On the Complexity of Some Geometric Problems With Fixed Parameters
From MaRDI portal
Publication:5856668
DOI10.7155/jgaa.00557zbMath1457.05111OpenAlexW3128467068MaRDI QIDQ5856668
Publication date: 29 March 2021
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00557
intersection graphuniversality theoremexistential theory of the realsrotation systemsimultaneous geometric embeddingMnëv
Related Items
The Complexity of Drawing a Graph in a Polygonal Region ⋮ RAC-drawability is \(\exists \mathbb{R} \)-complete
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sphere and dot product representations of graphs
- Fixed points, Nash equilibria, and the existential theory of the reals
- Simple realizability of complete abstract topological graphs in P
- Thickness and colorability of geometric graphs
- Area-efficient static and incremental graph drawings
- On simultaneous planar graph embeddings
- Order properties of lines in the plane and a conjecture of G. Ringel
- Uniform oriented matroids without the isotopy property
- Some provably hard crossing number problems
- The computational complexity of some problems of linear algebra
- Mnëv's universality theorem revisited
- Simple realizability of complete abstract topological graphs simplified
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- On the Computational Complexity of Upward and Rectilinear Planarity Testing
- Drawing Simultaneously Embedded Graphs with Few Bends
- On the Complexity of the Planar Slope Number Problem
- Reconstructing Point Set Order Types from Radial Orderings
- Complexity of Some Geometric and Topological Problems
- Oriented Matroids
- Complexity of Geometric k-Planarity for Fixed k
- The Complexity of Simultaneous Geometric Graph Embedding
- Simultaneous Geometric Graph Embeddings
- Drawing Partially Embedded and Simultaneously Planar Graphs
- Representing graphs by disks and balls (a survey of recognition-complexity results)
