Some provably hard crossing number problems
From MaRDI portal
polynomial-time algorithmarrangementtight boundpseudolinesNPcrossing drawingcrossing number problemsdrawing a graph
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Other problems of combinatorial convexity (52A37)
Recommendations
- scientific article; zbMATH DE number 1047749
- SOFSEM 2005: Theory and Practice of Computer Science
- scientific article; zbMATH DE number 2061148
- Hardness of approximation for crossing number
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- scientific article; zbMATH DE number 1054768
- Crossing Numbers and Parameterized Complexity
- Crossing Number Problems
- Crossing Number is NP-Complete
- New bounds on crossing numbers
Cites work
- scientific article; zbMATH DE number 432759 (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?)
- scientific article; zbMATH DE number 3394958 (Why is no real title available?)
- Bounds for rectilinear crossing numbers
- Crossing Number Problems
- Crossing Number is NP-Complete
- Intersection graphs of segments
- Multidimensional Sorting
- New results on rectilinear crossing numbers and plane embeddings
- On the combinatorial classification of nondegenerate configurations in the plane
- Polynomial realization of pseudoline arrangements
- Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
- Proof of a conjecture of Burr, Grünbaum, and Sloane
- Rectilinear drawings of graphs
- Semispaces of configurations, cell complexes of arrangements
- Teilungen der Ebenen durch Geraden oder topologische Geraden
- There are asymptotically far fewer polytopes than we thought
- Toward a theory of crossing numbers
- Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
Cited in
(48)- Crossing numbers of beyond-planar graphs
- Crossing numbers of beyond-planar graphs
- A simple proof that the \((n^{2} - 1)\)-puzzle is hard
- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- An ILP-based Proof System for the Crossing Number Problem
- Improved approximations of crossings in graph drawings
- Crossing minimization in perturbed drawings
- Crossing minimization in perturbed drawings
- An optimality criterion for the crossing number
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- The Complexity of Drawing Graphs on Few Lines and Few Planes
- Approximating the rectilinear crossing number
- Mathematical programs for drawing nonplanar graphs in the plane
- On the Pseudolinear Crossing Number
- Beyond the Existential Theory of the Reals
- Crossing numbers and stress of random graphs
- The complexity of drawing a graph in a polygonal region
- Topological art in simple galleries
- On the maximum crossing number
- Crossing number for graphs with bounded pathwidth
- Crossing minimization for symmetries
- \(k\)-level crossing minimization is NP-hard for trees
- Crossing Number Problems
- On the crossing number of complete graphs
- Approximating the maximum rectilinear crossing number
- Crossing Numbers of Beyond-Planar Graphs Revisited
- Simultaneous embedding of embedded planar graphs
- On the complexity of some geometric problems with fixed parameters
- On the realisability of double-cross matrices by polylines in the plane
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Approximating the rectilinear crossing number
- The complexity of tensor rank
- Parameterized analysis and crossing minimization problems
- A practical algorithm with performance guarantees for the art gallery problem
- Drawing borders efficiently
- Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
- Fixed points, Nash equilibria, and the existential theory of the reals
- The Crossing Number of Graphs: Theory and Computation
- scientific article; zbMATH DE number 2061148 (Why is no real title available?)
- The complexity of drawing a graph in a polygonal region
- On the complexity of recognizing nerves of convex sets
- Extending drawings of graphs to arrangements of pseudolines
- Which crossing number is it anyway?
- Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
- Smoothing the Gap Between NP and ER
- Recognition and complexity of point visibility graphs
- The crossing number of locally twisted cubes \(L T Q_n\)
- scientific article; zbMATH DE number 7525513 (Why is no real title available?)
This page was built for publication: Some provably hard crossing number problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1176321)
