Some provably hard crossing number problems

DOI10.1007/BF02574701zbMath0765.68202MaRDI QIDQ1176321

Bienstock, Daniel

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

zbMATH Keywords

polynomial-time algorithmarrangementtight boundpseudolinesNPcrossing drawingcrossing number problemsdrawing a graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) 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)

Related Items

The Complexity of Drawing a Graph in a Polygonal Region ⋮ SIMULTANEOUS EMBEDDING OF EMBEDDED PLANAR GRAPHS ⋮ Smoothing the Gap Between NP and ER ⋮ Crossing Numbers of Beyond-Planar Graphs Revisited ⋮ Parameterized analysis and crossing minimization problems ⋮ The crossing number of locally twisted cubes \(L T Q_n\) ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ Approximating the Rectilinear Crossing Number ⋮ Topological art in simple galleries ⋮ On the Pseudolinear Crossing Number ⋮ Unnamed Item ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ Crossing numbers and stress of random graphs ⋮ The complexity of drawing a graph in a polygonal region ⋮ Crossing number for graphs with bounded pathwidth ⋮ Recognition and complexity of point visibility graphs ⋮ Fixed points, Nash equilibria, and the existential theory of the reals ⋮ Unnamed Item ⋮ The complexity of tensor rank ⋮ Crossing numbers of beyond-planar graphs ⋮ Crossing numbers of beyond-planar graphs ⋮ Approximating the Maximum Rectilinear Crossing Number ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem ⋮ The Crossing Number of Graphs: Theory and Computation ⋮ Approximating the rectilinear crossing number ⋮ On the Complexity of Some Geometric Problems With Fixed Parameters ⋮ Which crossing number is it anyway? ⋮ On the crossing number of complete graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Teilungen der Ebenen durch Geraden oder topologische Geraden
• Semispaces of configurations, cell complexes of arrangements
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
• Proof of a conjecture of Burr, Grünbaum, and Sloane
• On the combinatorial classification of nondegenerate configurations in the plane
• Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
• Intersection graphs of segments
• Multidimensional Sorting
• Crossing Number is NP-Complete
• There are asymptotically far fewer polytopes than we thought
• Polynomial realization of pseudoline arrangements
• Rectilinear drawings of graphs
• New results on rectilinear crossing numbers and plane embeddings
• Bounds for rectilinear crossing numbers
• Toward a theory of crossing numbers
• Crossing Number Problems