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, Heraklion, Crete, Greece , pp. 38-49 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_5).
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 diﬀerent combinatorial viewpoints. On the one hand, we develop min-max formulas involving efﬁciently computable lower and upper bounds. These min-max results are the ﬁrst 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.
Repository Staff Only: item control page