Deciding Parity of Graph Crossing Number

DOI10.1137/17M1137231zbMath1393.05087WikidataQ60198463 ScholiaQ60198463MaRDI QIDQ4578013

Petr Hliněný, Carsten Thomassen

Publication date: 7 August 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

crossing numberNP-hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (1)

Parameterized analysis and crossing minimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Crossing numbers of graphs with rotation systems
• Construction of crossing-critical graphs
• Computing crossing numbers in quadratic time
• Hardness of approximation for crossing number
• The graph crossing number and its variants: a survey
• Crossing number is hard for cubic graphs
• The graph genus problem is NP-complete
• Crossing Number is Hard for Kernelization
• Crossing Number is NP-Complete
• The Minor Crossing Number
• On the parity of crossing numbers
• Crossing numbers of sequences of graphs II: Planar tiles
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• The crossing number of K5,n

This page was built for publication: Deciding Parity of Graph Crossing Number