English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Computing Geometric Minimum-Dilation Graphs Is NP-Hard

MPS-Authors
/persons/resource/persons44874

Kutz,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Klein, R., & Kutz, M. (2007). Computing Geometric Minimum-Dilation Graphs Is NP-Hard. In M. Kaufmann, & D. Wagner (Eds.), Graph Drawing (pp. 196-207). Berlin: Springer.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1EAA-3
Abstract
Consider a geometric graph $G$, drawn with straight lines in the plane. For every pair $a$,$b$ of vertices of $G$, we compare the shortest-path distance between $a$ and $b$ in $G$ (with Euclidean edge lengths) to their actual Euclidean distance in the plane. The worst-case ratio of these two values, for all pairs of vertices, is called the vertex-to-vertex dilation of $G$. We prove that computing a minimum-dilation graph that connects a given $n$-point set in the plane, using not more than a given number $m$ of edges, is an $NP$-hard problem, no matter if edge crossings are allowed or forbidden. In addition, we show that the minimum dilation tree over a given point set may in fact contain edge crossings.