Degree Constrained Book Embeddings

A of a graph consists of a linear ordering of the vertices along a line in 3-space (the ), and an assignment of edges to half-planes with the spine as boundary (the ), so that edges assigned to the same page can be drawn on that page without crossings. Given a graph = (), let : → ℕ be a function such that 1 ≤ () ≤ deg(). We present a Las Vegas algorithm which produces a book embedding of with pages, such that at most () edges incident to a vertex are on a single page. This result generalises that of S. M. Malitz [Graphs with edges have pagenumber . , 17(1):71—84, 1994.]