Approximating Gromov-Hausdorff Distance in Planar Graphs

Date

2020-05

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Many concepts in computer science can be represented as metric graphs, and Gromov-Hausdorff distance offers a natural way to measure the additive distortion between any metric spaces. However, there are no known polynomial time algorithms to compute or approximate this distance for general graphs. Even in metric trees, it is NP-Hard to compute or even approximate it within a constant factor of 3. This thesis provides a constant factor approximation for Gromov-Hausdorff distance between planar graphs whose edges are a constant factor larger than their Gromov-Hausdorff distance. A constant factor approximation for functional distortion distance between Contour trees with long edges is also provided.

Description

Keywords

Graph algorithms, Computational complexity, Trees (Graph theory), Metric spaces

Citation

URI

https://hdl.handle.net/2249.1/157867

Collections

University of Texas at Dallas