Embedding graphs in books: a survey

Embedding a graph in a book is an arrangement of vertices in a line along the spine of the book and edges on the pages in such a way that edges residing on the same page do not cross. Each graph has many different embeddings in books. The embedding with the minimum number of pages is optimum. This paper is a survey of problems dealing with embedding graphs in books. The author considers planar graphs, i.e. outerplanar graphs, sub-hamiltonians, series-parallel graphs, D-ary trees, and Xtrees (d-depth); square grids; nonplanar graphs; i.e. FFT networks with N input vertices Benes networks with N input vertices, pinwheel graphs and Boolean n-cube; and meshes of cliques, complete graphs. The computational complexity of the problems is mentioned. Some examples of optimum graph embeddings in books are presented. The problem of embedding a graph in a book is very important from the technical point of view. Optimisation of graph embeddings may be important in several technical applications, e.g. sorting with parallel stacks, fault-tolerant processor arrays design, and layout problems with application to very large scale integration (VLSI).