Crossing Number is Hard for Cubic Graphs

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	HLINĚNÝ Petr
Year of publication	2006
Type	Article in Periodical
Magazine / Source	Journal of Combinatorial Theory, Ser B
MU Faculty or unit	Faculty of Informatics
Citation
Web	http://dx.doi.org/10.1016/j.jctb.2005.09.009
Field	General mathematics
Keywords	crossing number; cubic graph; NP-completeness
Description	It was proved by [Garey and Johnson, 1983] that computing the crossing number of a graph is an $NP$-hard problem. Their reduction, however, used parallel edges and vertices of very high degrees. We prove here that it is $NP$-hard to determine the crossing number of a simple $3$-connected cubic graph. In particular, this implies that the minor-monotone version of the crossing number problem is also $NP$-hard, which has been open till now.
Related projects:	Highly Parallel and Distributed Computing Systems