CrossingCritical Graphs and PathWidthHliněný, Petr (2002) CrossingCritical Graphs and PathWidth. In: Graph Drawing 9th International Symposium, GD 2001, September 2326, 2001 , pp. 102114(Official URL: http://dx.doi.org/10.1007/3540458484_9). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540458484_9
AbstractThe crossing number cr( $G$) of a graph $G$, is the smallest possible number of edgecrossings in a drawing of $G$ in the plane. A graph $G$ is crossingcritical if cr ( $G$e)$<({\rm cr}$ $G$) for all edges $e$ of $G$. G. Salazar conjectured in 1999 that crossingcritical graphs have pathwidth bounded by a function of their crossing number, which roughly means that such graphs are made up of small pieces joined in a linear way on small cutsets. That conjecture was recently proved by the author [9]. Our paper presents that result together with a brief sketch of proof ideas. The main focus of the paper is on presenting a new construction of crossingcritical graphs, which, in particular, gives a nontrivial lower bound on the pathwidth. Our construction may be interesting also to other areas concerned with the crossing number.
Actions (login required)
