Crossing number is hard for cubic graphs

DOI10.1016/j.jctb.2005.09.009zbMath1092.05016OpenAlexW2028446993WikidataQ56032473 ScholiaQ56032473MaRDI QIDQ2496198

Petr Hliněný

Publication date: 12 July 2006

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2005.09.009

zbMATH Keywords

NP-completeness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (23)

Two recursive inequalities for crossing numbers of graphs ⋮ Determining the edge metric dimension of the generalized Petersen graph \(P(n, 3)\) ⋮ Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics ⋮ Outer 1-planar graphs ⋮ Star-struck by fixed embeddings: modern crossing number heuristics ⋮ There are no cubic graphs on 26 vertices with crossing number 10 or 11 ⋮ Parameterized analysis and crossing minimization problems ⋮ Deciding Parity of Graph Crossing Number ⋮ Inapproximability ratios for crossing number ⋮ Bounding the tripartite‐circle crossing number of complete tripartite graphs ⋮ Hardness of approximation for crossing number ⋮ Orthogonal drawings and crossing numbers of the Kronecker product of two cycles ⋮ Planar crossing numbers of graphs of bounded genus ⋮ Algorithms for the Hypergraph and the Minor Crossing Number Problems ⋮ Approximating the Crossing Number of Toroidal Graphs ⋮ On the red/blue spanning tree problem ⋮ Crossing numbers of graphs with rotation systems ⋮ Toroidal grid minors and stretch in embedded graphs ⋮ Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing ⋮ The crossing number of \(K_{1,m,n}\) ⋮ Crossing Number of Graphs with Rotation Systems ⋮ Approximating the Maximum Rectilinear Crossing Number ⋮ Connecting the dots (with minimum crossings)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing crossing numbers in quadratic time
• [https://portal.mardi4nfdi.de/wiki/Publication:3156923 The crossing number ofCm �Cn is as conjectured forn ?m(m + 1)]
• Crossing Number is NP-Complete
• [https://portal.mardi4nfdi.de/wiki/Publication:4888117 The crossing number ofC5 �Cn]
• Graph Drawing

This page was built for publication: Crossing number is hard for cubic graphs