Crossing-Number Critical Graphs have Bounded Path-width

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 ” binary tree. This assertion was conjectured earlier by Salazar in [J. Geelen, B. Richter, G. Salazar, Embedding grids on surfaces, submitted, 2000]