Discrete Mathematics & Theoretical Computer Science
Volume 6 n° 2 (2004), pp. 339-358
| author: | Vida Dujmović and David R. Wood |
|---|---|
| title: | On Linear Layouts of Graphs |
| keywords: | graph layout, graph drawing, stack layout, queue layout, arch layout, book embedding, queue-number, stack-number, page-number, book-thickness |
| 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. If your browser does not display the abstract correctly (because of the different mathematical symbols) you can look it up in the PostScript or PDF files. |
| reference: | Vida Dujmović and David R. Wood (2004), On Linear Layouts of Graphs, Discrete Mathematics and Theoretical Computer Science 6, pp. 339-358 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dm060210.ps.gz (207 K) |
| ps-source: | dm060210.ps (721 K) |
| pdf-source: | dm060210.pdf (206 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.
Automatically produced on Thu Jul 29 14:20:54 CEST 2004 by gustedt