ICS Theory Group

Fall 2016: Theory Seminar
DBH, Room 1300, 1:00pm

Oct 21, 2016:

Track Layout is Hard

William E. Devanny

We show that testing whether a given graph has a 3-track layout is hard, by characterizing the bipartite 3-track graphs in terms of leveled planarity. Additionally, we investigate the parameterized com- plexity of track layouts, showing that past methods used for book lay- outs do not work to parameterize the problem by treewidth or almost- tree number but that the problem is (non-uniformly) fixed-parameter tractable for tree-depth. We also provide several natural classes of bipar- tite planar graphs, including the bipartite outerplanar graphs, square- graphs, and dual graphs of arrangements of monotone curves, that always have 3-track layouts.

Joint work with Michael J. Bannister, Vida Dujmović, David Eppstein, and David R. Wood