Stars and Bonds in Crossing-Critical Graphs

The structure of all known infinite families of crossing-critical graphs has led to the conjecture that crossing-critical graphs have bounded bandwidth. If true, this would imply that crossing-critical graphs have bounded degree, that is, that they cannot contain subdivisions of K1, n for arbitrarily large n. In this paper we prove two results that revolve around this conjecture. On the positive side, we show that crossing-critical graphs cannot contain subdivisions of K2, n for arbitrarily large n. On the negative side, we show that there are graphs with arbitrarily large maximum degree that are 2-crossing-critical in the projective plane. © 2008 Elsevier B.V. All rights reserved.

VIVO