Adding One Edge to Planar Graphs Makes Crossing Number Hard

摘要

A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show that it is NP-hard to compute the crossing number of near-planar graphs. The main idea in the reduction is to consider the problem of simultaneously drawing two planar graphs inside a disk, with some of its vertices fixed at the boundary of the disk. This approach can be used to prove hardness of some other geometric problems. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hliněný.