On the obfuscation complexity of planar graphs

DOI10.1016/j.tcs.2008.02.032zbMath1155.68059OpenAlexW2080201242MaRDI QIDQ924163

Oleg Verbitsky

Publication date: 28 May 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.02.032

zbMATH Keywords

computational complexityplanar graphscombinatorial gamesstraight line drawings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Related Items (9)

Untangling polygons and graphs ⋮ Maximum rectilinear crossing number of uniform hypergraphs ⋮ Untangling circular drawings: algorithms and complexity ⋮ Untangling planar graphs from a specified vertex position-Hard cases ⋮ Approximating the Maximum Rectilinear Crossing Number ⋮ Geometry and Generation of a New Graph Planarity Game ⋮ On Collinear Sets in Straight-Line Drawings ⋮ A polynomial bound for untangling geometric planar graphs ⋮ Untangling a planar graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the cardinality of the maximum matchings of planar graphs
• Untangling a polygon
• A Theorem on Planar Graphs
• A Polynomial Bound for Untangling Geometric Planar Graphs
• Untangling a Planar Graph
• Moving Vertices to Make Drawings Plane
• Crossing patterns of segments

This page was built for publication: On the obfuscation complexity of planar graphs