### On Linear Layouts of Graphs

*Vida Dujmović, David R. Wood*

#### Abstract

In a total order of the vertices of a graph, two edges with no endpoint in common can be *crossing*, *nested*, or *disjoint*. A *k-stack* (respectively, *k-queue*, *k-arch*) *layout* of a graph consists of a total order of the vertices, and a partition of the edges into k sets of pairwise non-crossing (non-nested, non-disjoint) edges. Motivated by numerous applications, stack layouts (also called *book embeddings*) and queue layouts are widely studied in the literature, while this is the first paper to investigate arch layouts.

Our main result is a characterisation of k-arch graphs as the *almost (k+1)-colourable* graphs; that is, the graphs G with a set S of at most k vertices, such that G \ S is (k+1)-colourable.

In addition, we survey the following fundamental questions regarding each type of layout, and in the case of queue layouts, provide simple proofs of a number of existing results. How does one partition the edges given a fixed ordering of the vertices? What is the maximum number of edges in each type of layout? What is the maximum chromatic number of a graph admitting each type of layout? What is the computational complexity of recognising the graphs that admit each type of layout?

A comprehensive bibliography of all known references on these topics is included.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page