|
Organizers |
Recent Results on Book Thickness of Graphs
by
Paul C. Kainen
Department of Mathematics, Georgetown University
The book thickness of a graph G is the chromatic number of the intersection graph formed by the (open) edges of G, minimized over all straightline drawings of G where the vertices lie on the unit circle. Shannon Overbay, in her 1998 thesis at Colorado State University, Fort Collins, showed that every bipartite planar graph has book thickness at most two through an argument based on Whitney's theorem (every planar triangulation with no separating triangles has a Hamiltonian cycle). We sketch a proof of Overbay's result and its applications.
Date received: May 16, 2002
Copyright © 2002 by the author(s). The author(s) of this work and the organizers of the conference have granted their consent to include this abstract in Topology Atlas. Document # cajk-04.