Crossing Number 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 HlinnA1/2 and Salazar (Graph Drawing GD'06). On the other hand, we show that it is NP-hard to compute a weighted version of the crossing number for near-planar graphs.
crossing number near-planar np-hardness almost planar planar separation dual distance facial distance