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 number; NP-hardness

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C10: Planar graphs; geometric and topological aspects of graph theory