Metric planarity testing problem shown to be computationally hard
Metric Planarity Testing is Hard
Data Structures and Algorithms
Summary
The paper deals with metric planarity testing, where the goal is to decide if a set of distances between points can come from a weighted planar graph. While checking if a graph is planar is easy and fast, the authors show that finding a planar graph that exactly matches given distances is very hard—so hard that no quick algorithm is likely to exist. They also provide very slow algorithms that do work, and a way to get an approximate solution quickly. This settles a long-standing open question raised over 20 years ago.
What this means in practice
- •For graph algorithm designers: Avoid efforts to find fast exact algorithms for metric planarity testing, since the problem is NP-hard and unlikely to have subexponential algorithms.
- •For network layout engineers: Use approximation algorithms to produce planar network designs that nearly preserve given distance requirements with guaranteed error bounds.
A theory result. No direct application yet.
Authors
Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak, Hung Le, Bartłomiej Lewandowski, Karol Węgrzycki
Abstract
A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for either a polynomial-time algorithm or an NP-hardness proof for metric planarity testing: given a metric space $(X,d_X)$, determine whether there exists an edge-weighted planar graph $G=(V,E,w)$ with $X\subseteq V$ that realizes the distances in $X$, meaning that $d_G(x,y)=d_X(x,y)$ for every $x,y\in X$. This question arose in the context of research on metric embeddings and their applications in computer science since the mid-1990s. Over the past few decades, polynomial-time algorithms have been developed for several special cases. In this work, we show that metric planarity testing is NP-hard, in sharp contrast to graph planarity testing. Our reduction yields a stronger result: under the Exponential Time Hypothesis (ETH), no $2^{o(n)}$-time algorithm for metric planarity testing exists, where $n$ is the number of points in the metric. To complement our ETH lower bound, we give two algorithmic results: (i) an algorithm for computing a metric planar embedding in $2^{\tilde{O}(n^2)}$ time and (ii) a $(1+ε)$-approximation algorithm in $2^{\tilde{O}(n)}$ time for any fixed $ε\in(0,1)$. The second algorithm produces a planar graph that preserves the input metric up to a factor of $(1+ε)$.