On Collinear Sets in Straight-Line Drawings
Publication:3104785
DOI10.1007/978-3-642-25870-1_27zbMath1341.05045OpenAlexW2138317300MaRDI QIDQ3104785
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
planarityNP-hardnesshardness of approximationstraight-line drawinguntanglingallocation problemmoving verticespoint-set embeddability
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
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