Crossing-Critical Graphs and Path-Width
by
Petr Hlineny
SMCS, Victoria University

The crossing number of a graph G, denoted by cr(G), is defined as 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) < cr(G) for all edges e of G. We prove that crossing-critical graphs have ``bounded path-width'' (by a function of the crossing number), which roughly means that such graphs are made up of small pieces joined in a linear way on small cut-sets. Equivalently, a crossing-critical graph cannot contain a subdivision of a large complete binary tree. This was conjectured by G. Salazar in 1999. We also show a construction of a new class of crossing-critical graphs that provides a nontrivial lower bound for this problem.

Date received: October 9, 2001