Track Layout Is Hard

Bannister, Michael J. and Devanny, William E. and Dujmović, Vida and Eppstein, David and Wood, David R. (2016) Track Layout Is Hard. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 499-510(Official URL:

Full text not available from this repository.


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, squaregraphs, and dual graphs of arrangements of monotone curves, that always have 3-track layouts.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.700 Layering
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.480 Layered

Actions (login required)

View Item View Item