A polynomial bound for untangling geometric planar graphs

DOI10.1007/S00454-008-9125-3MaRDI QIDQ1042452zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Stefan Langerman, Pat Morin, David R. Wood

Publication date 14 December 2009

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0710.1641

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Polytopes and polyhedra (52Bxx) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: To untangle a geometric graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos [Discrete Comput. Geom., 2002] asked if every n-vertex geometric planar graph can be untangled while keeping at least n^epsilon vertices fixed. We answer this question in the affirmative with epsilon=1/4. The previous best known bound was Omega((log n / loglog n)^{1/2}). We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least (n/3)^{1/2} vertices fixed, while the best upper bound was O(nlog n)^{2/3}. We answer a question of Spillner and Wolff [arXiv:0709.0170 2007] by closing this gap for untangling trees. In particular, we show that for infinitely many values of n, there is an n-vertex geometric tree that cannot be untangled while keeping more than 3(n^{1/2}-1) vertices fixed. Moreover, we improve the lower bound to (n/2)^{1/2}.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: A polynomial bound for untangling geometric planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1042452)