Dominance drawings for DAGs with bounded modular width

DOI10.1007/978-3-031-23101-8_5MaRDI QIDQ6169511zbMATH OpenOpenAlexFDO

Authors Giacomo Ortali, Ioannis G. Tollis

Publication date 14 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-23101-8_5

zbMATH Keywords

(weak) dominance drawingsFPT-algorithmsmodular width

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• One-sided weak dominance drawing
• Parameterized algorithms for directed modular width
• An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification
• DAG-width is PSPACE-complete
• Small superpatterns for dominance drawing

Cites work

• A decomposition theorem for partially ordered sets
• Area requirement and symmetry display of planar upward drawings
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 6472574 (Why is no real title available?)
• scientific article; zbMATH DE number 3318560 (Why is no real title available?)
• Maximal dimensional partially ordered sets. I: Hiraguchi's theorem
• Modular decomposition and transitive orientation
• Parameterized algorithms for directed modular width
• Parameterized Algorithms for Modular-Width
• Partially Ordered Sets
• The Complexity of the Partial Order Dimension Problem

Cited in

(2)

• A fixed-parameter algorithm for dominance drawings of DAGs
• On planar straight-line dominance drawings

This page was built for publication: Dominance drawings for DAGs with bounded modular width

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