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

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