## Crossing-Critical Graphs and Path-Width
Hlinený, Petr
(2002)
Full text not available from this repository. ## AbstractThe crossing number cr( $G$) of a graph $G$, is the smallest possible number of edge-crossings in a drawing of $G$ in the plane. A graph $G$ is crossing-critical if cr ( $G$-e)$<({\rm cr}$ $G$) for all edges $e$ of $G$. G. Salazar conjectured in 1999 that crossing-critical graphs have path-width 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 cut-sets. 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 crossing-critical graphs, which, in particular, gives a nontrivial lower bound on the path-width. Our construction may be interesting also to other areas concerned with the crossing number.
Repository Staff Only: item control page References |