Crossing Minimization in Book Embeddings

Abstract: In a p-page book drawing, the vertices of the graph are placed on the x-axis (the spine), and the edges are drawn entirely in the upper half-plane. Each edge is then assigned one of p colors (the pages). The crossing number of a p-page book drawing is the sum of the number of crossings in each of the pages.

We consider the problems of, crossing minimization, which is to determine the p-page crossing number or minimum number of crossings in a p-page drawing, and p-page planarity, which is to determine whether a graph has a p-page drawing without any crossings. Crossing minimization and 2-page planarity are known to be NP-hard. We show that the problem of {1,2}-page crossing minimization and 2-page planarity are fixed-parameter tractable for various parameters related to treewidth.

Joint work with David Eppstein and Joseph A. Simons