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 complexity of track layouts, showing that past methods used for book layouts 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 bipartite planar graphs, including the bipartite outerplanar graphs, square-graphs, and dual graphs of arrangements of monotone curves, that always have 3-track layouts.
展开▼
