Fixed-parameter algorithms for computing RAC drawings of graphs

DOI10.1007/978-3-031-49275-4_5MaRDI QIDQ6618251zbMATH OpenFDO

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

Publication date 14 October 2024

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

zbMATH Keywords

feedback edge numberfixed-parameter tractabilityRAC drawingsvertex cover 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

• 2-layer right angle crossing drawings
• A characterization of complete bipartite RAC graphs
• Algorithmic meta-theorems for restrictions of treewidth
• Algorithms in real algebraic geometry
• An alternative method to crossing minimization on hierarchical graphs
• Computing crossing numbers in quadratic time
• Crossing Number is NP-Complete
• Drawing graphs with right angle crossings
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• Exact crossing number parameterized by vertex cover
• Fundamentals of parameterized complexity
• Graph minors. III. Planar tree-width
• Graph theory
• scientific article; zbMATH DE number 7559402 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• scientific article; zbMATH DE number 7651192 (Why is no real title available?)
• Improved upper bounds for vertex cover
• Linear time solvable optimization problems on graphs of bounded clique-width
• New algorithms for maximum disjoint paths based on tree-likeness
• On RAC drawings of graphs with one bend per edge
• On the perspectives opened by right angle crossing drawings
• Parameterized algorithms
• Parameterized algorithms for book embedding problems
• Parameterized algorithms for queue layouts
• Parameterized complexity of 1-planarity
• RAC drawings of graphs with low degree
• RAC-drawability is \(\exists \mathbb{R} \)-complete
• Right Angle Crossing Drawings of Graphs
• Sparsity. Graphs, structures, and algorithms
• The power of cut-based parameters for computing edge-disjoint paths
• The straight-line RAC drawing problem is NP-hard

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

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