On the complexity of some geometric problems with fixed parameters

DOI10.7155/JGAA.00557MaRDI QIDQ5856668zbMATH OpenOpenAlexFDO

Authors Marcus Schaefer

Publication date 29 March 2021

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00557

zbMATH Keywords

intersection graphuniversality theoremexistential theory of the realsrotation systemsimultaneous geometric embeddingMnëv

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• The complexity of simultaneous geometric graph embedding
• The complexity of drawing a graph in a polygonal region
• Simultaneous embedding of embedded planar graphs
• Simultaneous embedding of embedded planar graphs
• The Complexity of Drawing Graphs on Few Lines and Few Planes

Cites work

• scientific article; zbMATH DE number 4142090 (Why is no real title available?)
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• Area-efficient static and incremental graph drawings
• Complexity of geometric \(k\)-planarity for fixed \(k\)
• Complexity of some geometric and topological problems
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Drawing partially embedded and simultaneously planar graphs
• Drawing simultaneously embedded graphs with few bends
• Fixed points, Nash equilibria, and the existential theory of the reals
• Mnëv's universality theorem revisited
• On simultaneous planar graph embeddings
• On the complexity of the planar slope number problem
• On the computational complexity of upward and rectilinear planarity testing
• Order properties of lines in the plane and a conjecture of G. Ringel
• Oriented Matroids
• Reconstructing Point Set Order Types from Radial Orderings
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Simple realizability of complete abstract topological graphs in P
• Simple realizability of complete abstract topological graphs simplified
• Simultaneous Geometric Graph Embeddings
• Some provably hard crossing number problems
• Sphere and dot product representations of graphs
• The complexity of simultaneous geometric graph embedding
• The computational complexity of some problems of linear algebra
• Thickness and colorability of geometric graphs
• Uniform oriented matroids without the isotopy property

Cited in

(11)

• Rotation systems and simple drawings in surfaces
• Geometric complexity of some location problems
• \(\forall\exists\mathbb {R}\)-completeness and area-universality
• On the complexity of simultaneous geometric embedding for edge-disjoint graphs
• Algorithmic complexity of a problem of idempotent convex geometry.
• The complexity of simultaneous geometric graph embedding
• RAC-drawability is \(\exists \mathbb{R} \)-complete
• The complexity of drawing a graph in a polygonal region
• The Complexity of Geometric Problems in High Dimension
• Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete
• Geometric thickness of multigraphs is \(\exists \mathbb{R} \)-complete

This page was built for publication: On the complexity of some geometric problems with fixed parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5856668)