Graph Labelings

Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming non-crossing chords. A book embedding is a circular permutation of the vertices together with a partition of the edges into pages. The pagenumber t (G) is the minimum number of pages in a book embedding of G. We present a general construction showing $t(K\sb{m,n}) \leq \lceil(m + 2n)/4\rceil$, which we conjecture to be optimal. We prove a result suggesting this is optimal for $m \geq 2n - 3$. For the most difficult case, $m = n$, we consider vertex permutations that are regular, i.e. place the vertices from each partite set into runs of equal size. Book embeddings with such orderings require $\lceil(7n - 2)/9\rceil$ pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Weaver, Margaret Lefevre

Contributors dc:contributor

• West, Douglas B.

• Mathematics
• Computer Science

Identifier

(UMI)AAI8823280

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/71268