Topology Atlas | Conferences

Knots in Washington XXXVII
January 19-20, 2014
George Washington University
Washington, DC, USA

Mieczyslaw K. Dabkowski (UT Dallas), Valentina Harizanov (GWU), Jozef H. Przytycki (GWU and UMCP), Yongwu Rong (GWU), Radmila Sazdanovic (NCSU), Alexander Shumakovitch (GWU), Hao Wu (GWU)

Conference Homepage

A folding technique for drawing circulant graphs in books
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,

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.