Prefer a chat interface with context about you and your work?
Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show the surprising fact that it is NP-hard to compute the crossing number of near-planar graphs. A graph is 1-planar if it has a drawing where every edge is crossed by at …