Crossing and Weighted Crossing Number of Near-Planar Graphs

Cabello, Sergio and Mohar, Bojan (2009) Crossing and Weighted Crossing Number of Near-Planar Graphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008 , pp. 38-49(Official URL:

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-00219-9_5
Classifications: G Algorithms and Complexity > G.420 Crossings

Actions (login required)

View Item View Item