### 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