Some provably hard crossing number problems
DOI10.1007/BF02574701zbMATH Open0765.68202MaRDI QIDQ1176321FDOQ1176321
Publication date: 25 June 1992
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131170
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
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)
Cites Work
- Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
- Bounds for rectilinear crossing numbers
- Title not available (Why is that?)
- Intersection graphs of segments
- Crossing Number is NP-Complete
- Title not available (Why is that?)
- Rectilinear drawings of graphs
- Title not available (Why is that?)
- Proof of a conjecture of Burr, Grünbaum, and Sloane
- Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
- Teilungen der Ebenen durch Geraden oder topologische Geraden
- Title not available (Why is that?)
- Multidimensional Sorting
- Semispaces of configurations, cell complexes of arrangements
- On the combinatorial classification of nondegenerate configurations in the plane
- Crossing Number Problems
- Toward a theory of crossing numbers
- There are asymptotically far fewer polytopes than we thought
- Polynomial realization of pseudoline arrangements
- New results on rectilinear crossing numbers and plane embeddings
Cited In (39)
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Crossing number for graphs with bounded pathwidth
- Crossing numbers and stress of random graphs
- The complexity of drawing a graph in a polygonal region
- Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
- Crossing numbers of beyond-planar graphs
- Crossing numbers of beyond-planar graphs
- Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
- The Crossing Number of Graphs: Theory and Computation
- The Complexity of Drawing a Graph in a Polygonal Region
- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- On the Pseudolinear Crossing Number
- A practical algorithm with performance guarantees for the art gallery problem
- The complexity of tensor rank
- A simple proof that the \((n^{2} - 1)\)-puzzle is hard
- On the Complexity of Some Geometric Problems With Fixed Parameters
- Approximating the Rectilinear Crossing Number
- The Complexity of Drawing Graphs on Few Lines and Few Planes
- Approximating the rectilinear crossing number
- Crossing Number Problems
- Title not available (Why is that?)
- Which crossing number is it anyway?
- On the crossing number of complete graphs
- The crossing number of locally twisted cubes \(L T Q_n\)
- Topological art in simple galleries
- Approximating the Maximum Rectilinear Crossing Number
- Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
- Crossing minimization for symmetries
- Parameterized analysis and crossing minimization problems
- Beyond the Existential Theory of the Reals
- An ILP-based Proof System for the Crossing Number Problem
- Title not available (Why is that?)
- An optimality criterion for the crossing number
- SIMULTANEOUS EMBEDDING OF EMBEDDED PLANAR GRAPHS
- Title not available (Why is that?)
- Recognition and complexity of point visibility graphs
- Smoothing the Gap Between NP and ER
- Fixed points, Nash equilibria, and the existential theory of the reals
- Crossing Numbers of Beyond-Planar Graphs Revisited
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)
