Upward and orthogonal planarity are W[1]-hard parameterized by treewidth

DOI10.1007/978-3-031-49275-4_14MaRDI QIDQ6618262zbMATH OpenFDO

Authors Bart M. P. Jansen, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov

Publication date 14 October 2024

Full work available at URL https://doi.org/10.1007/978-3-031-49275-4_14

zbMATH Keywords

parameterized complexityrectilinear planaritytreewidthupward planarity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• Algorithms for graphs embeddable with few crossings per edge
• Algorithms – ESA 2004
• An SPQR-tree-like embedding representation for upward planarity
• Atomic Embeddability, Clustered Planarity, and Thickenability
• Efficient Planarity Testing
• Handbook of graph drawing and visualization
• scientific article; zbMATH DE number 2123122 (Why is no real title available?)
• HV-planarity: algorithms and complexity
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On the computational complexity of upward and rectilinear planarity testing
• On the path-width of planar graphs
• Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
• Optimal Upward Planarity Testing of Single-Source Digraphs
• Orthogonal planarity testing of bounded treewidth graphs
• Parameterized algorithms
• Parameterized complexity of graph planarity with restricted cyclic orders
• Planar rectilinear drawings of outerplanar graphs in linear time
• Problems hard for treewidth but easy for stable gonality
• Rectilinear planarity of partial 2-trees
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Spirality and Optimal Orthogonal Drawings
• Synchronized planarity with applications to constrained planarity problems
• Testing gap \(k\)-planarity is NP-complete
• Testing upward planarity of partial 2-trees
• Triangulating planar graphs while keeping the pathwidth small
• Upward Planar Drawing of Single-Source Acyclic Digraphs
• Upward spirality and upward planarity testing

Cited in

(5)

• Parameterized problems complete for nondeterministic FPT time and logarithmic space
• On the parameterized complexity of bend-minimum orthogonal planarity
• Rectilinear-upward planarity testing of digraphs
• XALP-completeness of parameterized problems on planar graphs
• On planar straight-line dominance drawings

This page was built for publication: Upward and orthogonal planarity are W[1]-hard parameterized by treewidth

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