On Collinear Sets in Straight-Line Drawings

DOI10.1007/978-3-642-25870-1_27zbMath1341.05045OpenAlexW2138317300MaRDI QIDQ3104785

Oleg Verbitsky, O. V. Ravskyj

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_27

zbMATH Keywords

planarityNP-hardnesshardness of approximationstraight-line drawinguntanglingallocation problemmoving verticespoint-set embeddability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (13)

Untangling polygons and graphs ⋮ Dual circumference and collinear sets ⋮ Untangling circular drawings: algorithms and complexity ⋮ Drawing Planar Graphs with Many Collinear Vertices ⋮ Drawing Graphs on Few Lines and Few Planes ⋮ Cubic Planar Graphs that cannot be Drawn on few Lines ⋮ Untangling planar graphs from a specified vertex position-Hard cases ⋮ Every collinear set in a planar graph is free ⋮ Unnamed Item ⋮ Aligned Drawings of Planar Graphs ⋮ 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
• Untangling planar graphs from a specified vertex position-Hard cases
• On triconnected and cubic plane graphs on given point sets
• Untangling polygons and graphs
• On the obfuscation complexity of planar graphs
• A polynomial bound for untangling geometric planar graphs
• Untangling a planar graph
• Longest cycles in 3-connected cubic graphs
• Analytic combinatorics of non-crossing configurations
• Untangling a polygon
• Shortness exponents of families of graphs
• On Collinear Sets in Straight-Line Drawings
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions

This page was built for publication: On Collinear Sets in Straight-Line Drawings