Crossing-Critical Graphs have Bounded Path-Width
by
Petr Hlineny
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. It is important to study crossing-critical graphs in order to understand what structural properties force the crossing number of a graph to be high; however, not much was known about them so far in general. 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 was conjectured earlier by Salazar in [J. Geelen, B. Richter, G. Salazar, Embedding grids in surfaces, manuscript, 2000].

reserach page

Date received: August 31, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafp-03.