Crossing number is hard for cubic graphs

被引：0

作者：

Hlineny, P

机构：

[1] Tech Univ Ostrava, Dept Comp Sci, VSB, CZ-70833 Ostrava, Czech Republic

[2] Charles Univ Prague, Inst Theoret Comp Sci, CR-11636 Prague 1, Czech Republic

来源：

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS | 2004年 / 3153卷

关键词：

crossing number; cubic graph; NP-completeness;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 cubic graph. In particular, this implies that the minor-monotone version of crossing number is also NP-hard, which has been open till now.

引用

页码：772 / 782

页数：11

共 11 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Fellows MR., 1989, CONT MATH, V89, P1

[3] CROSSING NUMBER IS NP-COMPLETE [J].

GAREY, MR ;

JOHNSON, DS .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (03) :312-316

[4]

GLEBSKY LY, IN PRESS J GRAPH THE

[5]

GROHE M, 2001, 32 ACM S THEOR COMP, P231

[6]

Guy R. K., 1969, PROOF TECHNIQUES GRA, P63

[7]

Harary F., 1973, NANTA MATH, V6, P58

[8]

Klesc M, 1996, J GRAPH THEOR, V22, P239, DOI 10.1002/(SICI)1097-0118(199607)22:3<239::AID-JGT4>3.0.CO

[9]

2-N

[10]

Pach J, 1998, ANN IEEE SYMP FOUND, P617

← 1 2 →