2012/03/27 by Sergio Cabello, Cabello, Sergio, Bojan Mohar +1 · 2 citations
Computer Science · Engineering · #Computational Geometry and Mesh Generation #3D Modeling in Geospatial Applications #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.1203.5944
A graph is near-planar if it can be obtained from a planar graph by adding an\nedge. We show the surprising fact that it is NP-hard to compute the crossing\nnumber of near-planar graphs. A graph is 1-planar if it has a drawing where\nevery edge is crossed by at most one other edge. We show that it is NP-hard to\ndecide whether a given near-planar graph is 1-planar. The main idea in both\nreductions is to consider the problem of simultaneously drawing two planar\ngraphs inside a disk, with some of its vertices fixed at the boundary of the\ndisk. This leads to the concept of anchored embedding, which is of independent\ninterest. As an interesting consequence we obtain a new, geometric proof of\nNP-completeness of the crossing number problem, even when restricted to cubic\ngraphs. This resolves a question of Hlin ven 'y.\n