MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Klein, Rolf
Kutz, Martin
dblp
dblp
Not MPG Author(s):
Klein, Rolf
Editor(s):
Kaufmann, Michael
Wagner, Dorothea
dblp
dblp
Not MPII Editor(s):
Kaufmann, Michael
Wagner, Dorothea
BibTeX cite key*:
KlKu2006a
Title, Booktitle
Title*:
Computing Geometric Minimum-Dilation Graphs Is NP-Hard
Booktitle*:
Graph Drawing : 14th International Symposium, GD 2006
Event, URLs
Conference URL::
Downloading URL:
http://www.springerlink.com/content/3705071u772l3375/fulltext.pdf
Event Address*:
Karlsruhe, Germany
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
18 September 2006
Event End Date:
20 September 2006
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4372
Number:
Month:
Pages:
196-207
Year*:
2007
VG Wort Pages:
ISBN/ISSN:
978-3-540-70903-9; 3-540-70903-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
URL for the Abstract:
http://dx.doi.org/10.1007/978-3-540-70904-6_20
Download
Access Level:
Internal

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{KlKu2006a,
AUTHOR = {Klein, Rolf and Kutz, Martin},
EDITOR = {Kaufmann, Michael and Wagner, Dorothea},
TITLE = {Computing Geometric Minimum-Dilation Graphs Is NP-Hard},
BOOKTITLE = {Graph Drawing : 14th International Symposium, GD 2006},
PUBLISHER = {Springer},
YEAR = {2007},
VOLUME = {4372},
PAGES = {196--207},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Karlsruhe, Germany},
ISBN = {978-3-540-70903-9},
; ISBN = {3-540-70903-7},
}


Entry last modified by Uwe Brahm, 02/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Pascal Schweitzer
Created
02/28/2007 02:21:34 PM
Revisions
9.
8.
7.
6.
5.
Editor(s)
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
07/07/2007 00:44:14
21.06.2007 17:18:33
20.06.2007 12:55:06
20.06.2007 12:01:44
20.06.2007 11:52:49