Document Open Access Logo

Distance Measures for Embedded Graphs

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.55.pdf
  • Filesize: 1.27 MB
  • 15 pages

Document Identifiers

Author Details

Hugo A. Akitaya
  • Department of Computer Science, Tufts University, Medford, MA, USA
Maike Buchin
  • Department of Mathematics, Ruhr University Bochum, Bochum, Germany
Bernhard Kilgus
  • Department of Mathematics, Ruhr University Bochum, Bochum, Germany
Stef Sijben
  • Department of Mathematics, Ruhr University Bochum, Bochum, Germany
Carola Wenk
  • Department of Computer Science, Tulane University, New Orleans, LA, USA

Funding

  • Akitaya, Hugo A.: Supported by National Science Foundation grants CCF-1422311 and CCF-1423615, and the Science Without Borders scholarship program.
  • Kilgus, Bernhard: Supported by the Deutsche Forschungsgemeinschaft (DFG), project BU 2419/3-1.
  • Wenk, Carola: Supported by National Science Foundation grant CCF-1618469.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.55

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Fréchet distance
  • graph comparison
  • embedded graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos, and Yusu Wang. Computing the Gromov-Hausdorff Distance for Metric Trees. ACM Trans. Algorithms, 14(2):24:1-24:20, April 2018. URL: https://doi.org/10.1145/3185466.
  2. Mahmuda Ahmed, Brittany T. Fasy, Kyle S. Hickmann, and Carola Wenk. Path-based distance for street map comparison. ACM Transactions on Spatial Algorithms and Systems, 28 pages, 2015. Google Scholar
  3. Mahmuda Ahmed, Brittany Terese Fasy, and Carola Wenk. Local Persistent Homology Based Distance Between Maps. In 22nd ACM SIGSPATIAL GIS, pages 43-52, 2014. Google Scholar
  4. Mahmuda Ahmed, Sophia Karagiorgou, Dieter Pfoser, and Carola Wenk. A comparison and evaluation of map construction algorithms using vehicle tracking data. GeoInformatica, 19(3):601-632, 2015. Google Scholar
  5. Mahmuda Ahmed, Sophia Karagiorgou, Dieter Pfoser, and Carola Wenk. Map Construction Algorithms. Springer, 2015. Google Scholar
  6. Mahmuda Ahmed and Carola Wenk. Constructing Street Networks from GPS Trajectories. In Proceedings of the 20th Annual European Conference on Algorithms, ESA'12, pages 60-71, Berlin, Heidelberg, 2012. Springer-Verlag. Google Scholar
  7. Hugo Akitaya, Maike Buchin, and Bernhard Kilgus. Distance Measures for Embedded Graphs - Revisited. In 35th European Workshop on Computational Geometry (EuroCG), 2019. Google Scholar
  8. Hugo A. Akitaya, Maike Buchin, Bernhard Kilgus, Stef Sijben, and Carola Wenk. Distance Measures for Embedded Graphs. CoRR, abs/1812.09095, 2018. URL: http://arxiv.org/abs/1812.09095.
  9. Helmut Alt, Alon Efrat, Günter Rote, and Carola Wenk. Matching planar maps. Journal of Algorithms, 49(2):262-283, 2003. Google Scholar
  10. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications, 5(1&2):75-91, 1995. Google Scholar
  11. Ayser Armiti and Michael Gertz. Geometric graph matching and similarity: A probabilistic approach. ACM International Conference Proceeding Series, June 2014. Google Scholar
  12. James Biagioni and Jakob Eriksson. Inferring Road Maps from Global Positioning System Traces: Survey and Comparative Evaluation. Transportation Research Record: Journal of the Transportation Research Board, 2291:61-71, 2012. Google Scholar
  13. Maike Buchin, Stef Sijben, and Carola Wenk. Distance Measures for Embedded Graphs. In Proc. 33rd European Workshop on Computational Geometry (EuroCG), pages 37-40, 2017. Google Scholar
  14. Otfried Cheong, Joachim Gudmundsson, Hyo-Sil Kim, Daria Schymura, and Fabian Stehn. Measuring the similarity of geometric graphs. In International Symposium on Experimental Algorithms, pages 101-112, 2009. Google Scholar
  15. Jonathan J. Davies, Alastair R. Beresford, and Andy Hopper. Scalable, Distributed, Real-Time Map Generation. IEEE Pervasive Computing, 5(4):47–54, 2006. Google Scholar
  16. David Duran, Vera Sacristán, and Rodrigo I. Silveira. Map Construction Algorithms: An Evaluation Through Hiking Data. In Proceedings of the 5th ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems, MobiGIS '16, pages 74-83, 2016. Google Scholar
  17. David Eppstein. Subgraph Isomorphism in Planar Graphs and Related Problems. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '95, pages 632-640, Philadelphia, PA, USA, 1995. Society for Industrial and Applied Mathematics. Google Scholar
  18. Sophia Karagiorgou and Dieter Pfoser. On vehicle tracking data-based road network generation. In 20th ACM SIGSPATIAL GIS, pages 89-98, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact