Untangling a planar graph

DOI10.1007/s00454-008-9130-6zbMath1188.05092OpenAlexW3103048564MaRDI QIDQ1042455

Alexander Wolff, Jan Kratochvíl, Yoshio Okamoto, Chan-Su Shin, Xavier Goaoc, Andreas Spillner

Publication date: 14 December 2009

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

Full work available at URL: https://doi.org/10.1007/s00454-008-9130-6

zbMATH Keywords

planaritygraph drawingNP-hardnesshardness of approximationstraight-line drawinguntanglingmoving verticespoint-set embeddability

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (13)

Lower and upper bounds for long induced paths in 3-connected planar graphs ⋮ Untangling polygons and graphs ⋮ Upper Bound Constructions for Untangling Planar Geometric Graphs ⋮ Dual circumference and collinear sets ⋮ Untangling circular drawings: algorithms and complexity ⋮ Drawing Planar Graphs with Many Collinear Vertices ⋮ \(\beta\)-stars or on extending a drawing of a connected subgraph ⋮ 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 ⋮ Planar drawings of fixed-mobile bigraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Untangling planar graphs from a specified vertex position-Hard cases
• On the obfuscation complexity of planar graphs
• Convex drawings of graphs with non-convex boundary constraints
• Planar graphs and poset dimension
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Intersection graphs of segments
• Generating rooted triangulations without repetitions
• Untangling a polygon
• Bemerkungen zum Vierfarbenproblem
• On Collinear Sets in Straight-Line Drawings
• Longest Increasing and Decreasing Subsequences
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• Efficient Planarity Testing
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Untangling polygons and graphs
• A Polynomial Bound for Untangling Geometric Planar Graphs
• Untangling a Planar Graph
• Moving Vertices to Make Drawings Plane
• Convex Maps
• Morphing orthogonal planar graph drawings
• Embedding planar graphs at fixed vertex locations

This page was built for publication: Untangling a planar graph