A polynomial bound for untangling geometric planar graphs

DOI10.1007/s00454-008-9125-3zbMath1188.05090arXiv0710.1641OpenAlexW3104828215MaRDI QIDQ1042452

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

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

zbMATH Keywords

geometric graphscrossingsuntangling

Mathematics Subject Classification ID

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

Related Items

Untangling polygons and graphs, Upper Bound Constructions for Untangling Planar Geometric Graphs, Dual circumference and collinear sets, Untangling circular drawings: algorithms and complexity, A center transversal theorem for hyperplanes and applications to graph drawing, Drawing Planar Graphs with Many Collinear Vertices, Untangling planar graphs from a specified vertex position-Hard cases, Every collinear set in a planar graph is free, Unnamed Item, Geometry and Generation of a New Graph Planarity Game, On Collinear Sets in Straight-Line Drawings

Cites Work

• Unnamed Item
• Untangling planar graphs from a specified vertex position-Hard cases
• How to draw a planar graph on a grid
• On the obfuscation complexity of planar graphs
• Convex drawings of graphs with non-convex boundary constraints
• Untangling a polygon
• Über eine Eigenschaft der ebenen Komplexe
• A decomposition theorem for partially ordered sets
• On Collinear Sets in Straight-Line Drawings
• Untangling polygons and graphs
• Untangling a Planar Graph
• Moving Vertices to Make Drawings Plane