Complexity of some geometric and topological problems
From MaRDI portal
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Recommendations
Cited in
(91)- The complexity of point configurations
- Complexity of triangulations of the projective space.
- \(\forall\exists\mathbb {R}\)-completeness and area-universality
- Order on order types
- The complexity of drawing a graph in a polygonal region
- Computational complexity of multi-player evolutionarily stable strategies
- Parameterized analysis and crossing minimization problems
- On compatible triangulations with a minimum number of Steiner points
- Treetopes and their graphs
- Stick graphs with length constraints
- Representing graphs and hypergraphs by touching polygons in 3D
- Variants of the segment number of a graph
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Termination of polynomial loops
- Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
- Approximating the rectilinear crossing number
- Realizing RCC8 networks using convex regions
- On the complexity of recognizing Stick, BipHook and max point-tolerance graphs
- Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations
- Approximating the maximum rectilinear crossing number
- Contact representations of planar graphs: extending a partial representation is hard
- Approximating the rectilinear crossing number
- How to draw a planarization
- On the Pseudolinear Crossing Number
- Complexity of linear circuits and geometry
- On the expressive power of query languages for matrices
- The Complexity of Geometric Problems in High Dimension
- scientific article; zbMATH DE number 4002078 (Why is no real title available?)
- Some complexity results in topology and analysis
- scientific article; zbMATH DE number 1859221 (Why is no real title available?)
- The complexity of drawing a graph in a polygonal region
- Smoothing the Gap Between NP and ER
- Crossing Numbers of Beyond-Planar Graphs Revisited
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- A crossing lemma for multigraphs
- Recognition and complexity of point visibility graphs
- Recognizing stick graphs with and without length constraints
- Complexity of geometric \(k\)-planarity for fixed \(k\)
- Recognizing Visibility Graphs of Triangulated Irregular Networks
- Fixed points, Nash equilibria, and the existential theory of the reals
- Hyperbolic Dimension and Decomposition Complexity
- How to draw a planarization
- An optimal algorithm for reconstructing point set order types from radial orderings
- On the complexity of some geometric problems with fixed parameters
- Oriented matroids and combinatorial neural codes
- Refining the hierarchies of classes of geometric intersection graphs
- Clique-width of point configurations
- Drawing graphs as spanners
- Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
- The real computational complexity of minmax value and equilibrium refinements in multi-player games
- Refining the hierarchies of classes of geometric intersection graphs
- \(P\) versus \(NP\) and geometry
- The Complexity of Drawing Graphs on Few Lines and Few Planes
- The Complexity of Angular Resolution
- NP-Hardness of Computing PL Geometric Category in Dimension 2
- Multidimensional Manhattan preferences
- On the complexity of recognizing nerves of convex sets
- IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?
- The complexity of the Hausdorff distance
- Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
- Simple realizability of complete abstract topological graphs in P
- Geometric thickness of multigraphs is \(\exists \mathbb{R} \)-complete
- The complexity of recognizing geometric hypergraphs
- On classifying continuous constraint satisfaction problems
- Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
- The complexity of iterated reversible computation
- Convex hulls of random order types
- A practical algorithm with performance guarantees for the art gallery problem
- Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
- The parametrized complexity of the segment number
- Intersection graphs and geometric objects in the plane
- Tractability conditions for numeric CSPs
- Improved hardness results for the clearing problem in financial networks with credit default swaps
- Geometric embeddability of complexes is \(\exists\mathbb{R}\)-complete
- Automated symmetric constructions in discrete geometry
- Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete
- A topological version of Schaefer's dichotomy theorem
- Some structural complexity results for \(\exists{\mathbb{R}} \)
- Pizza sharing is PPA-hard
- Drawn tree decomposition: new approach for graph drawing problems
- Termination of triangular polynomial loops
- On the complexity of simultaneous geometric embedding for edge-disjoint graphs
- Recognition of unit segment and polyline graphs is \(\exists \mathbb{R} \)-complete
- The complexity of recognizing geometric hypergraphs
- The complexity of tensor rank
- A practical algorithm with performance guarantees for the art gallery problem
- The existential theory of the reals with summation operators
- Segment intersection representations, level planarity and constrained ordering problems
- An introduction to geometric complexity theory
- Algorithmic complexity of a problem of idempotent convex geometry.
- Complexity of finite sequences of zeros and ones and geometry of finite spaces of functions
This page was built for publication: Complexity of some geometric and topological problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557891)
