Adding one edge to planar graphs makes crossing number and 1-planarity\n hard

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\\v{e}n\\'y.\n