Track Layouts, Layered Path Decompositions, and Leveled Planarity
Track Layouts, Layered Path Decompositions, and Leveled Planarity
复制标题
轨道布局、分层路径分解和水平平面度
作者：
Michael J. Bannister;William E. Devanny;V. Dujmović;D. Eppstein;D. Wood
我们研究了两种类型的图形布局，轨道布局和分层路径分解，以及它们的相关参数轨道数和分层路径宽度之间的关系。我们使用这两种类型的布局来表征水平平面图，这是具有没有虚拟顶点的平面水平图的图。从已知的水平平面性的 NP 完备性可知，轨道数和分层路径宽度也是 NP 完备的，即使对于使这些参数变得不平凡的最小常数参数值也是如此。我们证明具有有界分层路径宽度的图包括外平面图、哈林图和方形图，但（尽管具有有界轨道数）串并联图不具有有界分层路径宽度。最后，我们研究了这些布局的参数化复杂性，表明过去用于书籍布局的方法不能通过树宽或几乎树数来参数化问题，但问题是（非均匀）固定参数可处理树深度。
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.