On Collinear Sets in Straight-Line Drawings

DOI10.1007/978-3-642-25870-1_27zbMath1341.05045MaRDI 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

planarity; NP-hardness; hardness of approximation; straight-line drawing; untangling; allocation problem; moving vertices; point-set embeddability

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Unnamed Item, Aligned Drawings of Planar Graphs, Cubic Planar Graphs that cannot be Drawn on few Lines, Untangling circular drawings: algorithms and complexity, Untangling planar graphs from a specified vertex position-Hard cases, Untangling polygons and graphs, A polynomial bound for untangling geometric planar graphs, Untangling a planar graph, Every collinear set in a planar graph is free, Dual circumference and collinear sets, Drawing Planar Graphs with Many Collinear Vertices, Drawing Graphs on Few Lines and Few Planes, On Collinear Sets in Straight-Line Drawings

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