
Accession Number : ADA189649
Title : Graph Labelings.
Descriptive Note : Doctoral thesis,
Corporate Author : ILLINOIS UNIV AT URBANA COORDINATED SCIENCE LAB
Personal Author(s) : Weaver, Margaret L
PDF Url : ADA189649
Report Date : 12 Jan 1988
Pagination or Media Count : 97
Abstract : Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming noncrossing 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 sub m,n) or (m + 2n)/4), which we conjecture to be optimal. Weprove a result suggesting this is optimal for m or = 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 (7n  2)/9) pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering.
Descriptors : *GRAPHS, CIRCULAR, EDGES, EMBEDDING, THESES, NETWORKS, SIZES(DIMENSIONS), PERMUTATIONS
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE