Two results on layered pathwidth and linear layouts

DOI10.7155/JGAA.00549MaRDI QIDQ5144880zbMATH OpenOpenAlexFDO

Authors Vida Dujmović, Pat Morin, Céline Yelle

Publication date 19 January 2021

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Layered pathwidth is a new graph parameter studied by Bannister et al (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts. Our first result shows that, for any graph $G$, the stack number of $G$ is at most four times the layered pathwidth of $G$. Our second result shows that any graph $G$ with track number at most three has layered pathwidth at most four. The first result complements a result of Dujmovi'c and Frati (2018) relating layered treewidth and stack number. The second result solves an open problem posed by Bannister et al (2015).

Recommendations

• Track layouts, layered path decompositions, and leveled planarity
• Separating layered treewidth and row treewidth
• PATHWIDTH AND LAYERED DRAWINGS OF TREES

Cites work

• scientific article; zbMATH DE number 1693470 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 2159655 (Why is no real title available?)
• Improved bounds for centered colorings
• Laying Out Graphs Using Queues
• Layout of Graphs with Bounded Tree-Width
• Layouts of Expander Graphs
• Planar graphs have bounded nonrepetitive chromatic number
• Planar graphs have bounded queue-number
• Shorter Labeling Schemes for Planar Graphs
• Straight-line grid drawings of 3-connected 1-planar graphs
• Structure of graphs with locally restricted crossings
• Track layout is hard
• Track layouts, layered path decompositions, and leveled planarity

Cited in

(4)

• Track layouts, layered path decompositions, and leveled planarity
• scientific article; zbMATH DE number 6131601 (Why is no real title available?)
• 2-Layer Graph Drawings with Bounded Pathwidth
• Forbidden patterns in mixed linear layouts

This page was built for publication: Two results on layered pathwidth and linear layouts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144880)