Parameterized complexity of graph planarity with restricted cyclic orders

DOI10.1016/J.JCSS.2023.02.007MaRDI QIDQ2698291zbMATH OpenOpenAlexFDO

Authors Giuseppe Liotta, Ignaz Rutter, Alessandra Tappini

Publication date 21 April 2023

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.jcss.2023.02.007

zbMATH Keywords

embedding constraintsfixed parameter tractabilitygraph algorithmsNodeTrix planarityplanarity testing

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• \((k, p)\)-planarity: a relaxation of hybrid planarity
• \((k,p)\)-planarity: a relaxation of hybrid planarity
• A fixed-parameter approach to 2-layer planarization
• A new perspective on clustered planarity as a combinatorial embedding problem
• Call routing and the ratcatcher
• ChordLink: a new hybrid visualization model
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Exact crossing number parameterized by vertex cover
• Graph minors. X: Obstructions to tree-decomposition
• scientific article; zbMATH DE number 2123122 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 6506583 (Why is no real title available?)
• HV-planarity: algorithms and complexity
• Intersection-link representations of graphs
• No-bend orthogonal drawings and no-bend orthogonally convex drawings of planar graphs (extended abstract)
• On the complexity of some colorful problems parameterized by treewidth
• On the computational complexity of upward and rectilinear planarity testing
• On the parameterized complexity of layered graph drawing
• On-Line Planarity Testing
• Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
• Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
• Orthogonal planarity testing of bounded treewidth graphs
• Parameterized algorithms
• Parameterized algorithms for book embedding problems
• Parameterized complexity of graph planarity with restricted cyclic orders
• Planarity for clustered graphs
• Planarity Testing and Optimal Edge Insertion with Embedding Constraints
• Quasi-upward planar drawings with minimum curve complexity
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Spirality and Optimal Orthogonal Drawings
• Synchronized planarity with applications to constrained planarity problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The NP-Completeness of Edge-Coloring
• Turning cliques into paths to achieve planarity
• Upward planarity testing
• Upward spirality and upward planarity testing

Cited in

(3)

• Upward and orthogonal planarity are W[1]-hard parameterized by treewidth
• Drawn tree decomposition: new approach for graph drawing problems
• Upward and rectilinear planarity are W[1]-hard parameterized by treewidth

Describes a project that uses

Uses Software

• NodeTrix

This page was built for publication: Parameterized complexity of graph planarity with restricted cyclic orders

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