Crossing-Critical Graphs and Path-Width

Hliněný, Petr (2002) Crossing-Critical Graphs and Path-Width. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001 , pp. 102-114(Official URL: http://dx.doi.org/10.1007/3-540-45848-4_9).

Full text not available from this repository.

Abstract

The 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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-45848-4_9
Classifications: Z Theory > Z.001 General
G Algorithms and Complexity > G.420 Crossings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/505

Actions (login required)

View Item View Item