DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2019.55

Distance Measures for Embedded Graphs

Authors: Hugo A. Akitaya, Maike Buchin, Bernhard Kilgus, Stef Sijben, and Carola Wenk

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract

We introduce new distance measures for comparing straight-line embedded graphs based on the Fréchet distance and the weak Fréchet distance. These graph distances are defined using continuous mappings and thus take the combinatorial structure as well as the geometric embeddings of the graphs into account. We present a general algorithmic approach for computing these graph distances. Although we show that deciding the distances is NP-hard for general embedded graphs, we prove that our approach yields polynomial time algorithms if the graphs are trees, and for the distance based on the weak Fréchet distance if the graphs are planar embedded. Moreover, we prove that deciding the distances based on the Fréchet distance remains NP-hard for planar embedded graphs and show how our general algorithmic approach yields an exponential time algorithm and a polynomial time approximation algorithm for this case. Our work combines and extends the work of Buchin et al. [Maike Buchin et al., 2017] and Akitaya et al. [Hugo Akitaya et al., 2019] presented at EuroCG.

Cite as

Hugo A. Akitaya, Maike Buchin, Bernhard Kilgus, Stef Sijben, and Carola Wenk. Distance Measures for Embedded Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{akitaya_et_al:LIPIcs.ISAAC.2019.55,
  author =	{Akitaya, Hugo A. and Buchin, Maike and Kilgus, Bernhard and Sijben, Stef and Wenk, Carola},
  title =	{{Distance Measures for Embedded Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.55},
  URN =		{urn:nbn:de:0030-drops-115517},
  doi =		{10.4230/LIPIcs.ISAAC.2019.55},
  annote =	{Keywords: Fr\'{e}chet distance, graph comparison, embedded graphs}
}

Search Results

Documents authored by Kilgus, Bernhard

Distance Measures for Embedded Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message