Graph Labelings.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 12, 1988
- Accession Number
- ADA189649
Entities
People
- Margaret L. Weaver
Organizations
- University of Illinois Urbana–Champaign