Complexity of Some Geometric and Topological Problems
From MaRDI portal
Publication:3557891
DOI10.1007/978-3-642-11805-0_32zbMath1284.68305OpenAlexW2131662609WikidataQ55894555 ScholiaQ55894555MaRDI QIDQ3557891
Publication date: 27 April 2010
Published in: Graph Drawing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-11805-0_32
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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Oriented matroids and combinatorial neural codes ⋮ The Complexity of Drawing a Graph in a Polygonal Region ⋮ An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings ⋮ Order on order types ⋮ Smoothing the Gap Between NP and ER ⋮ Crossing Numbers of Beyond-Planar Graphs Revisited ⋮ Parameterized analysis and crossing minimization problems ⋮ Contact Representations of Planar Graphs: Extending a Partial Representation is Hard ⋮ On the Expressive Power of Query Languages for Matrices ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ The Complexity of Angular Resolution ⋮ On compatible triangulations with a minimum number of Steiner points ⋮ Multidimensional Manhattan preferences ⋮ 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 ⋮ Approximating the Rectilinear Crossing Number ⋮ Treetopes and their graphs ⋮ Simple realizability of complete abstract topological graphs in P ⋮ Ham-sandwich cuts for abstract order types ⋮ 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 ⋮ How to Draw a Planarization ⋮ Stick graphs with length constraints ⋮ Representing graphs and hypergraphs by touching polygons in 3D ⋮ Variants of the segment number of a graph ⋮ On the Pseudolinear Crossing Number ⋮ Unnamed Item ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ The complexity of drawing a graph in a polygonal region ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ Complexity of Geometric k-Planarity for Fixed k ⋮ Termination of polynomial loops ⋮ Recognition and complexity of point visibility graphs ⋮ Tractability conditions for numeric CSPs ⋮ Fixed points, Nash equilibria, and the existential theory of the reals ⋮ Recognizing Visibility Graphs of Triangulated Irregular Networks ⋮ How to Draw a Planarization ⋮ The real computational complexity of minmax value and equilibrium refinements in multi-player games ⋮ Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\) ⋮ The complexity of tensor rank ⋮ Realizing RCC8 networks using convex regions ⋮ Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Clique-width of point configurations ⋮ Drawing graphs as spanners ⋮ Approximating the Maximum Rectilinear Crossing Number ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem ⋮ Approximating the rectilinear crossing number ⋮ On the Complexity of Some Geometric Problems With Fixed Parameters ⋮ A crossing lemma for multigraphs ⋮ Computational complexity of multi-player evolutionarily stable strategies
