|
Organizers |
A folding technique for drawing circulant graphs in books
by
Paul C. Kainen
Georgetown University
A folding technique for laying out the vertices of some circulants in an outerplanar drawing makes it easy to find good drawings of these graphs in books with low book thickness and crossing number. Let C(n, {1, k}) denote the circulant with edges of length 1 and k, while crk(G) is the k-page crossing number of G in a book with k pages.
Theorem 1. For k ≥ 2 an integer and r ≥ 2 even, the book thickness of C(rk, {1, k}) is at most 4.
Theorem 2. For k ≥ 3 odd and r ≥ 2 even, cr2(C(rk, {1, k}) ≤ r(k-2) and cr3(C(rk, {1, k}) ≤ r/2.
The folding technique achieving these results is described for the case r = 2 in the author's technical report, Circular layouts for crossing-free matchings, http://www9.georgetown.edu/faculty/kainen/circlayouts.pdf
Date received: January 8, 2014
Copyright © 2014 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 # cbid-22.