文章基本信息
- 标题：Distance Measures for Embedded Graphs
- 本地全文：下载
- 作者：Hugo A. Akitaya ; Maike Buchin ; Bernhard Kilgus 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2019
- 卷号：149
- 页码：1-15
- DOI：10.4230/LIPIcs.ISAAC.2019.55
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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.
- 关键词：Fréchet distance; graph comparison; embedded graphs
