A polynomial bound for untangling geometric planar graphs

DOI10.1007/S00454-008-9125-3zbMATH Open1188.05090arXiv0710.1641OpenAlexW3104828215MaRDI QIDQ1042452FDOQ1042452

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)

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}.

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

Recommendations

• Untangling polygons and graphs
• Untangling polygons and graphs
• Upper Bound Constructions for Untangling Planar Geometric Graphs
• Upper bound constructions for untangling planar geometric graphs
• Untangling a planar graph

zbMATH Keywords

geometric graphscrossingsuntangling

Mathematics Subject Classification ID

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)

Cites Work

• Über eine Eigenschaft der ebenen Komplexe
• Title not available (Why is that?)
• How to draw a planar graph on a grid
• A decomposition theorem for partially ordered sets
• Convex drawings of graphs with non-convex boundary constraints
• Untangling a polygon
• On collinear sets in straight-line drawings
• Untangling planar graphs from a specified vertex position-Hard cases
• Untangling a Planar Graph
• Moving Vertices to Make Drawings Plane
• On the obfuscation complexity of planar graphs
• Untangling polygons and graphs

Cited In (17)

• Untangling a Planar Graph
• Untangling planar graphs from a specified vertex position-Hard cases
• Drawing planar graphs with many collinear vertices
• Untangling polygons and graphs
• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
• On collinear sets in straight-line drawings
• Upper bound constructions for untangling planar geometric graphs
• Geometry and generation of a new graph planarity game
• Untangling a planar graph
• Every collinear set in a planar graph is free
• Untangling polygons and graphs
• Upper Bound Constructions for Untangling Planar Geometric Graphs
• A center transversal theorem for hyperplanes and applications to graph drawing
• Title not available (Why is that?)
• Dual circumference and collinear sets
• Dual circumference and collinear sets
• Untangling circular drawings: algorithms and complexity

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)