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 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 sub m,n) or (m + 2n)/4), which we conjecture to be optimal. We-prove 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