Crossing Number is Hard for Cubic Graphs

Warning

This publication doesn't include Faculty of Arts. 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:

You are running an old browser version. We recommend updating your browser to its latest version.