Local and Union Page Numbers
share
We introduce the novel concepts of local and union book embeddings, and, as the corresponding graph parameters, the local page number pn_ℓ(G) and the union page number pn_u(G). Both parameters are relaxations of the classical page number pn(G), and for every graph G we have pn_ℓ(G) ≤ pn_u(G) ≤ pn(G). While for pn(G) one minimizes the total number of pages in a book embedding of G, for pn_ℓ(G) we instead minimize the number of pages incident to any one vertex, and for pn_u(G) we instead minimize the size of a partition of G with each part being a vertex-disjoint union of crossing-free subgraphs. While pn_ℓ(G) and pn_u(G) are always within a multiplicative factor of 4, there is no bound on the classical page number pn(G) in terms of pn_ℓ(G) or pn_u(G). We show that local and union page numbers are closer related to the graph's density, while for the classical page number the graph's global structure can play a much more decisive role. We introduce tools to investigate local and union book embeddings in exemplary considerations of the class of all planar graphs and the class of graphs of tree-width k. As an incentive to pursue research in this new direction, we offer a list of intriguing open problems.
READ FULL TEXT