文章基本信息

标题：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