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