Noncrossing Subgraphs in Topological Layouts
Jan Kratochvı́l, Anna Lubiw, Jaroslav Nešetřil · SIAM Journal on Discrete Mathematics · 1991
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.