Crossing Number is Hard for Cubic Graphs
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Combinatorial Theory, Ser B |
| MU Faculty or unit | |
| 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: |