Track Layouts, Layered Path Decompositions, and Leveled Planarity

Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)

Abstract

We investigate two types of graph layouts, track layouts and layered path decompositions, and the relations between their associated parameters track-number and layered pathwidth. We use these two types of layouts to characterize leveled planar graphs, which are the graphs with planar leveled drawings with no dummy vertices. It follows from the known NP-completeness of leveled planarity that track-number and layered pathwidth are also NP-complete, even for the smallest constant parameter values that make these parameters nontrivial. We prove that the graphs with bounded layered pathwidth include outerplanar graphs, Halin graphs, and squaregraphs, but that (despite having bounded track-number) series–parallel graphs do not have bounded layered pathwidth. Finally, we investigate the parameterized complexity of these 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.

Original languageEnglish
Pages (from-to)1561-1583
Number of pages23
JournalAlgorithmica
Volume81
Issue number4
DOIs
Publication statusPublished - 2019

Keywords

  • Almost-tree number
  • Halin graphs
  • Layered path decompositions
  • Layered pathwidth
  • Leveled planar graphs
  • Outerplanar graphs
  • Parameterized complexity
  • Squaregraphs
  • Track layouts
  • Track-number
  • Tree-depth
  • Treewidth
  • Unit disc graphs

Cite this

Bannister, M. J., Devanny, W. E., Dujmović, V., Eppstein, D., & Wood, D. R. (2019). Track Layouts, Layered Path Decompositions, and Leveled Planarity. Algorithmica, 81(4), 1561-1583. https://doi.org/10.1007/s00453-018-0487-5