arXiv preprint ·
Metric Planarity Testing is Hard
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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+ε)$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Cascade: GPU-Accelerated Out-of-Core Suffix Array Construction for LLM Corpora
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
Optimal High Probability Bounds for Random Order Online Sorting
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.