Winter 2015: Theory Seminar
ICS, Room 243, 1:00pm
March 6, 2015:

Fixed-Parameter Tractable Algorithms for Crossing Minimization in Book Embeddings

Michael Bannister

Abstract: We investigate exact crossing minimization problems for 1-page and 2-page book drawings of graphs. In both 1-page and 2-page book drawings, the vertices of the graph are drawn in the xy-plane along the x-axis and the edges are drawn as continuous curves that do not cross the x-axis. In 1-page book drawings, the edges must be drawn in the upper half-plane (y > 0), whereas in 2-page drawings the edges may also be drawn in the lower half-plane (y < 0). To improve the readability of such drawings, we would like to minimize the number of crossing between edges. These optimization problems are known to be NP-hard and therefore are unlikely to have polynomial-time algorithms. However, we show that for graphs that are "tree-like", polynomial-time algorithms do exist for 1-page and 2-page crossing minimization. In particular, we show that these crossing minimization problems are fixed-parameter tractable with respect to treewidth and the k-almost-tree parameter.