Computing Geometric Minimum-Dilation Graphs Is NP-Hard

DOI10.1007/978-3-540-70904-6_20zbMath1185.05045OpenAlexW1744317798MaRDI QIDQ3595495

Rolf Klein, Martin Kuetz

Publication date: 28 August 2007

Published in: Graph Drawing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70904-6_20

zbMATH Keywords

dilationplane graphNP-hardnessgeometric networkstretch factorspanning ratio

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

On the dilation spectrum of paths, cycles, and trees ⋮ Optimal Embedding into Star Metrics ⋮ DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES ⋮ Computing Minimum Dilation Spanning Trees in Geometric Graphs ⋮ On plane geometric spanners: a survey and open problems ⋮ Minimum weight Euclidean \(t\)-spanner is NP-hard ⋮ Sparse geometric graphs with small dilation ⋮ Computing a minimum-dilation spanning tree is NP-hard

This page was built for publication: Computing Geometric Minimum-Dilation Graphs Is NP-Hard