On the Parameterized Complexity of Layered Graph Drawing

2007/12/06 by Vida Dujmović, Michael R. Fellows, Matthew Kitching +7 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Bounded function #Combinatorics #Computational Geometry and Mesh Generation #Crossing number (knot theory) #Discrete mathematics #Graph #Graph Theory and Algorithms #Graph drawing #Line graph #Mathematics #Parameterized complexity #Pathwidth #Span (engineering) #Theory of computation #Time complexity

paper · doi:10.1007/s00453-007-9151-1

openalex publication_date 2007/12/06 · crossref created 2007/12/06 · crossref issued 2007/12/07 · crossref published 2007/12/07 · crossref published-online 2007/12/07 · crossref published-print 2008/10/01 · crossref deposited 2020/04/29 · openalex created_date 2025/10/10 · crossref indexed 2026/02/10 · openalex updated_date 2026/07/23

Citations

• Laying Out Graphs Using Queues
• Computing crossing number in linear time
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Methods for Visual Understanding of Hierarchical System Structures
• Computing crossing numbers in quadratic time
• Layout of Graphs with Bounded Tree-Width
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Graduate Texts in Mathematics

Cited by

• Straightening out planar poly-line drawings
• Pathwidth [wikipedia]