The pagewidth of trivalent planar graphs (Q2276971)

A book imbedding of a graph is an ordering of the vertices along the spine of a book (the intersection line of the pages) and an imbedding of the edges on the pages (each edge on one page). The pagewidth of a book imbedding is the maximum number of edges crossing any perpendicular to the spline of the book, over all pages. The author shows that there exist trivalent n-vertex planar graphs G(n) having the property that every 2- page imbedding of G(n) has pagewidth \(\omega\) (n). The result demonstrates that, in some cases, small pagenumber can be achieved only at the expense of large pagewidth. This has relevance to fault-tolerant VLSI design.