Fixed-parameter algorithms for computing RAC drawings of graphs

DOI10.1007/978-3-031-49275-4_5MaRDI QIDQ6618251

Florian Schager, Robert Ganian, Sebastian Röder, Cornelius Brand

Publication date: 14 October 2024

zbMATH Keywords

fixed-parameter tractabilityvertex cover numberRAC drawingsfeedback edge number

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• 2-layer right angle crossing drawings
• Improved upper bounds for vertex cover
• Drawing graphs with right angle crossings
• A characterization of complete bipartite RAC graphs
• Graph minors. III. Planar tree-width
• Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
• New algorithms for maximum disjoint paths based on tree-likeness
• Computing crossing numbers in quadratic time
• Linear time solvable optimization problems on graphs of bounded clique-width
• RAC-drawability is \(\exists \mathbb{R} \)-complete
• Exact crossing number parameterized by vertex cover
• On RAC drawings of 1-planar graphs
• The power of cut-based parameters for computing edge-disjoint paths
• An Alternative Method to Crossing Minimization on Hierarchical Graphs
• Graph Theory
• The Straight-Line RAC Drawing Problem is NP-Hard
• Crossing Number is NP-Complete
• Algorithmic Meta-theorems for Restrictions of Treewidth
• Parameterized Complexity of 1-Planarity
• Right Angle Crossing Drawings of Graphs
• Parameterized Algorithms for Queue Layouts
• Parameterized Algorithms for Book Embedding Problems
• Parameterized Algorithms
• On the Perspectives Opened by Right Angle Crossing Drawings
• On RAC drawings of graphs with one bend per edge
• Algorithms in real algebraic geometry
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• RAC drawings of graphs with low degree

This page was built for publication: Fixed-parameter algorithms for computing RAC drawings of graphs