On the parameterized complexity of layered graph drawing

DOI10.1007/s00453-007-9151-1zbMath1170.68028OpenAlexW2922321031WikidataQ57359905 ScholiaQ57359905MaRDI QIDQ958215

Vida Dujmović, David R. Wood, Giuseppe Liotta, Catherine McCartin, Matthew Kitching, S. H. Whitesides, Michael R. Fellows, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond

Publication date: 2 December 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9151-1

zbMATH Keywords

crossing-free \(h\)-layer drawings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

A faster fixed parameter algorithm for two-layer crossing minimization ⋮ Parameterized Algorithms for Queue Layouts ⋮ Combining intensification and diversification strategies in VNS. An application to the vertex separation problem ⋮ Variable neighborhood search for the vertex separation problem ⋮ Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth ⋮ Parameterized analysis and crossing minimization problems ⋮ Two-layer planarization parameterized by feedback edge set ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Parameterized approaches to orthogonal compaction ⋮ Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs ⋮ 2-Layer Graph Drawings with Bounded Pathwidth ⋮ Sketched representations and orthogonal planarity of bounded treewidth graphs ⋮ Homotopy height, grid-major height and graph-drawing height ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Ranking and Drawing in Subexponential Time ⋮ Track layouts, layered path decompositions, and leveled planarity ⋮ Cubic Planar Graphs that cannot be Drawn on few Lines ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Drawing Planar Graphs with Reduced Height ⋮ Unnamed Item ⋮ A linear edge kernel for two-layer crossing minimization ⋮ On Layered Fan-Planar Graph Drawings ⋮ Horton-Strahler number, rooted pathwidth and upward drawings of trees ⋮ Orthogonal planarity testing of bounded treewidth graphs ⋮ 2-Layer k-Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of embedding planar graphs to minimize certain distance measures
• Interval graphs and maps of DNA
• Edge crossings in drawings of bipartite graphs
• Drawing graphs in two layers
• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• Computing crossing numbers in quadratic time
• A fixed-parameter approach to 2-layer planarization
• Crossing Number is NP-Complete
• Drawing Graphs on Two and Three Lines
• Experiments with the Fixed-Parameter Approach for Two-Layer Planarization
• Two-Layer Planarization: Improving on Parameterized Algorithmics
• Laying Out Graphs Using Queues
• Crossing Theory and Hierarchy Mapping
• Approximation algorithms for NP-complete problems on planar graphs
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Layout of Graphs with Bounded Tree-Width
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph Drawing