The Complexity of Drawing Graphs on Few Lines and Few Planes
From MaRDI portal
Publication:6075709
DOI10.7155/jgaa.00630zbMath1522.05327OpenAlexW2489413438MaRDI QIDQ6075709
Alexander Wolff, Oleg Verbitsky, Fabian Lipp, O. V. Ravskyj, Steven Chaplick, Krzysztof Fleszar
Publication date: 20 September 2023
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00630
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)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sphere and dot product representations of graphs
- Recognition and complexity of point visibility graphs
- Fixed points, Nash equilibria, and the existential theory of the reals
- Hardness of embedding simplicial complexes in \(\mathbb R^d\)
- Some provably hard crossing number problems
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Intersection graphs of segments
- Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
- Representing graphs and hypergraphs by touching polygons in 3D
- Line and plane cover numbers revisited
- Variants of the segment number of a graph
- Drawings of planar graphs with few slopes and segments
- The complexity of drawing graphs on few lines and few planes
- A Note on Minimum-Segment Drawings of Planar Graphs
- On the Complexity of the Planar Slope Number Problem
- Embeddability in the 3-Sphere Is Decidable
- Noncrossing Subgraphs in Topological Layouts
- Bounds for the vertex linear arboricity
- Minimum-weight triangulation is NP-hard
- Complexity of Some Geometric and Topological Problems
- PROPERTIES OF ARRANGEMENT GRAPHS
- Drawing graphs on few lines and few planes
- Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity
- Geometry Revealed
- Drawing Graphs with Few Arcs
