Other formats:
BibTeX
LaTeX
RIS
@article{589862,
author = {Hliněný, Petr},
article_location = {Amsterdam},
article_number = {4},
keywords = {crossing number; cubic graph; NP-completeness},
language = {eng},
issn = {0095-8956},
journal = {Journal of Combinatorial Theory, Ser B},
title = {Crossing Number is Hard for Cubic Graphs},
url = {http://dx.doi.org/10.1016/j.jctb.2005.09.009},
volume = {96},
year = {2006}
}
TY - JOUR
ID - 589862
AU - Hliněný, Petr
PY - 2006
TI - Crossing Number is Hard for Cubic Graphs
JF - Journal of Combinatorial Theory, Ser B
VL - 96
IS - 4
SP - 455-471
EP - 455-471
PB - Elsevier B.V.
SN - 00958956
KW - crossing number
KW - cubic graph
KW - NP-completeness
UR - http://dx.doi.org/10.1016/j.jctb.2005.09.009
N2 - 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.
ER -
HLINĚNÝ, Petr. Crossing Number is Hard for Cubic Graphs. \textit{Journal of Combinatorial Theory, Ser B}. Amsterdam: Elsevier B.V., 2006, vol.~96, No~4, p.~455-471. ISSN~0095-8956.
|
