Complexity of Some Geometric and Topological Problems
From MaRDI portal
Publication:3557891
DOI10.1007/978-3-642-11805-0_32zbMath1284.68305WikidataQ55894555 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A crossing lemma for multigraphs, The Complexity of Drawing a Graph in a Polygonal Region, Smoothing the Gap Between NP and ER, Crossing Numbers of Beyond-Planar Graphs Revisited, Recognizing Stick Graphs with and without Length Constraints, Complexity of Geometric k-Planarity for Fixed k, Recognizing Visibility Graphs of Triangulated Irregular Networks, How to Draw a Planarization, Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem, An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings, Refining the hierarchies of classes of geometric intersection graphs, The real computational complexity of minmax value and equilibrium refinements in multi-player games, 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, On the Complexity of Some Geometric Problems With Fixed Parameters, Oriented matroids and combinatorial neural codes, The Complexity of Drawing Graphs on Few Lines and Few Planes, The Complexity of Angular Resolution, Multidimensional Manhattan preferences, Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality, Recognition and complexity of point visibility graphs, Fixed points, Nash equilibria, and the existential theory of the reals, Simple realizability of complete abstract topological graphs in P, Tractability conditions for numeric CSPs, The complexity of tensor rank, Order on order types, Ham-sandwich cuts for abstract 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, On the Expressive Power of Query Languages for Matrices
