Atlas home || Conferences | Abstracts | about Atlas

21st Cumberland Conference on Graph Theory, Combinatorics, and Computing ---In Honor of Mike Plummer's 70th Birthday
May 15-17, 2008
Vanderbilt University
Nashville, TN, USA

Organizers
Mark Ellingham and Gexin Yu

View Abstracts
Conference Homepage

Minor crossing numbers
by
Eva Czabarka
University of South Carolina, Columbia
Coauthors: Drago Bokal (University of Maribor) László A. Székely (University of South Carolina) Imrich Vro (Slovak Academy of Sciences)

mcr(G), the minor crossing number of G is the minimal crossing number over all graphs that contain G as a minor. There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection width method and the embedding method. We have adapt all three methods to the minor crossing number. In addition, we show that for the string crossing number str(G), str(G) ≤ 4mcr(G) and mcr(G) ≤ str(G)+|E(G)|-|V(G)|+t(G)|, where t(G) is the number of tree components of G. Our results imply for the n-dimensional hypercube Qn that mcr(Qn)=W([(4n)/n ]).

Date received: February 24, 2008

Copyright © 2008 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 # cawn-04.