2-Layer Graph Drawings with Bounded Pathwidth

DOI10.7155/JGAA.00647MaRDI QIDQ6181954zbMATH OpenFDO

Authors David R. Wood

Publication date 20 December 2023

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/2207.06656

zbMATH Keywords

bipartite graphs of bounded pathwidth

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We determine which properties of 2-layer drawings characterise bipartite graphs of bounded pathwidth.

Recommendations

• scientific article; zbMATH DE number 1303024
• Two-layer drawings of bipartite graphs
• scientific article; zbMATH DE number 1796980
• On the parameterized complexity of layered graph drawing
• Drawing bipartite graphs in two layers with specified crossings
• Compact layered drawings of general directed graphs
• Layered drawing of undirected graphs with generalized port constraints
• Layered Drawing of Undirected Graphs with Generalized Port Constraints
• scientific article; zbMATH DE number 1974106
• Curve-constrained drawings of planar graphs

Cites work

• 2-Layer k-Planar Graphs
• 2-layer right angle crossing drawings
• A decomposition theorem for partially ordered sets
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• A fixed-parameter approach to 2-layer planarization
• A partial k-arboretum of graphs with bounded treewidth
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• Crossing number for graphs with bounded pathwidth
• Crossing-number critical graphs have bounded path-width
• Drawing graphs in two layers
• Drawing Graphs on Two and Three Lines
• Edge crossings in drawings of bipartite graphs
• Graph Minors I: A Short Proof of the Path-width Theorem
• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 2159655 (Why is no real title available?)
• scientific article; zbMATH DE number 3412664 (Why is no real title available?)
• Layout of Graphs with Bounded Tree-Width
• On the one-sided crossing minimization in a bipartite graph with large degrees
• On the parameterized complexity of layered graph drawing
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• Quickly excluding a forest
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• Track layouts, layered path decompositions, and leveled planarity
• Two results on layered pathwidth and linear layouts

Cited in

(3)

• Drawing graphs with k vertices per face: complexity and algorithms
• On the complexity of recognizing k^+-real face graphs
• Forbidden patterns in mixed linear layouts

This page was built for publication: 2-Layer Graph Drawings with Bounded Pathwidth

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