School Seminars and Colloquia

Extremal Graph Theory for Book Embeddings

Discrete Structures and Algorithms (Seminar)

by Jessica McClintock


Institution: The University of Melbourne
Date: Wed 26th September 2012
Time: 1:00 PM
Location: Old Geology Theatre 2

Abstract: A "book-embedding" of a graph consists of a linear ordering of the vertices, with the edges partitioned into sets such that no edges in the same set cross. The ordering of vertices is referred to as the "spine" of the book, while the sets of non-crossing edges are called "pages". The minimum number of pages in a book-embedding of a given graph is the "pagenumber" of that graph. Book-embeddings are also commonly referred to as "stack-layouts", as they model operations on a stack. Many of the applications of book-embeddings arise from this relation.

After introducing some of the concepts relevant to the study of book-embeddings and discussing some of their applications, we will describe some of the main results on the pagenumber for classes of graphs, with particular attention being given to results on the pagenumber of planar graphs. We will then give a brief discussion of extremal graph theory, along with some results from this field that consider the extremal graph size with regards to other graph invariants, before discussing extremal results with regards to the pagenumber of graphs.

The original results of this thesis consider "edge-maximal book-embeddings", which are book-embeddings to which no edge can be added without increasing the pagenumber. We prove that the minimum number of edges in a 3-page edge-maximal book-embedding with n vertices is \(\lceil{7n/2}\rceil\). We give an upper bound of \((k+4)n/2\) and a lower bound of \(\sqrt{kn/2}\) on the minimum number of edges in a k-page edge-maximal book-embedding.