Parameterized complexity of graph planarity with restricted cyclic orders

DOI10.1016/j.jcss.2023.02.007OpenAlexW4324102010MaRDI QIDQ2698291

Alessandra Tappini, Ignaz Rutter, Giuseppe Liotta

Publication date: 21 April 2023

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

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

zbMATH Keywords

fixed parameter tractabilitygraph algorithmsplanarity testingembedding constraintsNodeTrix planarity

Mathematics Subject Classification ID

Computer science (68-XX)

Uses Software

• NodeTrix

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of some colorful problems parameterized by treewidth
• A new perspective on clustered planarity as a combinatorial embedding problem
• On the parameterized complexity of layered graph drawing
• Graph minors. X: Obstructions to tree-decomposition
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Call routing and the ratcatcher
• HV-planarity: algorithms and complexity
• Turning cliques into paths to achieve planarity
• Upward planarity testing
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Simultaneous FPQ-ordering and hybrid planarity testing
• Orthogonal planarity testing of bounded treewidth graphs
• Quasi-upward planar drawings with minimum curve complexity
• ChordLink: a new hybrid visualization model
• Exact crossing number parameterized by vertex cover
• No-bend orthogonal drawings and no-bend orthogonally convex drawings of planar graphs (extended abstract)
• NodeTrix planarity testing with small clusters
• A fixed-parameter approach to 2-layer planarization
• \((k,p)\)-planarity: a relaxation of hybrid planarity
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Computing NodeTrix Representations of Clustered Graphs
• Upward Spirality and Upward Planarity Testing
• The NP-Completeness of Edge-Coloring
• Spirality and Optimal Orthogonal Drawings
• On-Line Planarity Testing
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• Parameterized Algorithms for Book Embedding Problems
• Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
• (k, p)-Planarity: A Relaxation of Hybrid Planarity
• Planarity Testing and Optimal Edge Insertion with Embedding Constraints
• Intersection-Link Representations of Graphs
• Parameterized Algorithms
• Parameterized complexity of graph planarity with restricted cyclic orders
• Planarity for clustered graphs

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