Track layouts, layered path decompositions, and leveled planarity

DOI10.1007/S00453-018-0487-5zbMath1421.68105arXiv1506.09145OpenAlexW3099033428MaRDI QIDQ1739109

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

Publication date: 25 April 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.09145

zbMATH Keywords

treewidthouterplanar graphsHalin graphsparameterized complexitytree-depthalmost-tree numberlayered path decompositionslayered pathwidthleveled planar graphssquare graphstrack layoutstrack-numberunit disc graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (23)

Clustered 3-colouring graphs of bounded degree ⋮ Parameterized Algorithms for Queue Layouts ⋮ On the queue number of planar graphs ⋮ Separating layered treewidth and row treewidth ⋮ The Rique-number of graphs ⋮ An improved upper bound on the queue number of planar graphs ⋮ The product structure of squaregraphs ⋮ Linear layouts of bipartite planar graphs ⋮ 2-Layer Graph Drawings with Bounded Pathwidth ⋮ Improved Bounds for Track Numbers of Planar Graphs ⋮ 4-connected triangulations on few lines ⋮ Line and plane cover numbers revisited ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Two Results on Layered Pathwidth and Linear Layouts ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Cubic Planar Graphs that cannot be Drawn on few Lines ⋮ 2-colored point-set embeddings of partial 2-trees ⋮ Better bounds for poset dimension and boxicity ⋮ 2-colored point-set embeddings of partial 2-trees ⋮ Planar Graphs of Bounded Degree Have Bounded Queue Number ⋮ Multilevel Planarity ⋮ Parameterized Algorithms for Queue Layouts ⋮ On Mixed Linear Layouts of Series-Parallel Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Clique minors in Cartesian products of graphs
• Sparsity. Graphs, structures, and algorithms
• Graph layouts via layered separators
• On the parameterized complexity of layered graph drawing
• Graph minors. I. Excluding a forest
• S-functions for graphs
• Edge crossings in drawings of bipartite graphs
• Layered separators in minor-closed graph classes with applications
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
• Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
• Genus, Treewidth, and Local Crossing Number
• Stack and Queue Layouts via Layered Separators
• Parameters Tied to Treewidth
• Combinatorics and Geometry of Finite and Infinite Squaregraphs
• Layouts of Expander Graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Laying Out Graphs Using Queues
• Parameterized Complexity of 1-Planarity
• Flat foldings of plane graphs with prescribed angles and edge lengths
• Orthogonal Tree Decompositions of Graphs
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• Graph Drawing
• Layout of Graphs with Bounded Tree-Width
• Structure of Graphs with Locally Restricted Crossings

This page was built for publication: Track layouts, layered path decompositions, and leveled planarity