Crossing and Weighted Crossing Number of Near-Planar Graphs

A nonplanar graph G is near-planar if it contains an edge e such that G − e is planar. The problem of determining the crossing number of a near-planar graph is exhibited from different combinatorial viewpoints. On the one hand, we develop min-max formulas involving efficiently computable lower and upper bounds. These min-max results are the first of their kind in the study of crossing numbers and improve the approximation factor for the approximation algorithm given by Hlinˇny e´ and Salazar (Graph Drawing GD 2006). On the other hand, we show that it is NP-hard to compute a weighted version of the crossing number for near-planar graphs