NONCROSSING SUBGRAPHS IN TOPOLOGICAL LAYOUTS

作     者：KRATOCHVIL, J LUBIW, A NESETRIL, J 

作者机构：CHARLES UNIV DEPT APPL MATH CS-11000 PRAGUE CZECHOSLOVAKIA UNIV WATERLOO DEPT COMP SCI WATERLOO N2L 3G1 ONTARIO CANADA 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1991年第4卷第2期

页      面：223-244页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：TOPOLOGICAL GRAPHS PLANAR LAYOUT ALGORITHMIC COMPLEXITY 

摘      要：The computational complexity of the following type of problems is studied. Given a topological layout (i.e., a drawing in the plane) of a graph, does it contain a noncrossing subgraph of a given type? It is conjectured that such problems are always NP-hard (provided planar subgraphs are looked for) regardless of the complexity of their nonplanar versions. This conjecture is verified for several cases in a very strong sense. In particular, it is shown that deciding the existence of a noncrossing path connecting two given vertices in a given topological layout of a 3-regular subgraph, as well as deciding the existence of a noncrossing cycle in such a layout are NP-complete problems. It is also proved that deciding the existence of a noncrossing k-factor in a topological layout of a (k + 1)-regular graph is NP-complete for k = 2, 3, 4, 5. For k = 1, this question is NP-complete in layouts of 3-regular graphs, while it is polynomial solvable for layouts of graphs with maximum degree two.