A nonplanar graph is near-planar if it contains an edge whose removal leaves a planar graph. 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ěný 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.
COBISS.SI-ID: 15261785
It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface ${\mathbb S}_g$ of genus $g$ grows asymptotically like $$c^{(g)}n^{5(g-1)/2-1}\gamma^n n!$$ where $c^{(g)})0$, and $\gamma \approx 27.23$ is the exponential growth rate of planar graphs. This generalizes the result for the planar case $g=0$, obtained by Gimenez and Noy. An analogous result for non-orientable surfaces is obtained. In addition, it is proved that several parameters of interest behave asymptotically as in the planar case. It follows, in particular, that a random graph embeddable in ${\mathbb S}_g$ has a unique 2-connected component of linear size with high probability.
COBISS.SI-ID: 15875673
The n-th crossing number of a graph G, denoted $cr_n(G)$, is the minimum number of crossings in a drawing of G on an orientable surface of genus n. We prove that for every $a)b)0$, there exists a graph G for which $cr_0(G) = a$, $cr_1(G) = b$, and $cr_2(G) = 0$. This provides support for a conjecture of Archdeacon et al. and resolves a problem of Salazar.
COBISS.SI-ID: 16051801