Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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