Geodesic
Fixed-Parameter Algorithms for Computing Bend-Restricted RAC Drawings of Graphs
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023 , Tome 28 (2024) no. 2, pp. 131-150.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In a right-angle crossing (RAC) drawing of a graph, each edge is represented as a polyline and edge crossings must occur at an angle of exactly $90^\circ$, where the number of bends on such polylines is typically restricted in some way. While structural and topological properties of RAC drawings have been the focus of extensive research and particular attention has been paid to RAC drawings with at most $0$, $1$, $2$ and $3$ bends per edge, little was known about the boundaries of tractability for computing such drawings. In this paper, we initiate the study of bend-restricted RAC drawings from the viewpoint of parameterized complexity. In particular, we establish that computing a RAC drawing of an input graph $G$ with at most $b$ bends where each edge $e$ has a prescribed upper-bound $0\leq \beta(e) \leq 3$ on the number of bends it can support (or determining that none exists) is: fixed-parameter tractable parameterized by the feedback edge number of $G$, and fixed-parameter tractable parameterized by $b$ plus the vertex cover number of $G$.
DOI : 10.7155/jgaa.v28i2.2995
Keywords: parameterized complexity, RAC drawings, bend-restricted drawings

Cornelius Brand 1 ; Robert Ganian 1 ; Sebastian Röder 1 ; Florian Schager 1

1 TU Wien 
@article{JGAA_2024_28_2_a6,
     author = {Cornelius Brand and Robert Ganian and Sebastian R\"oder and Florian Schager},
     title = {Fixed-Parameter {Algorithms} for {Computing} {Bend-Restricted} {RAC} {Drawings} of {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {131--150},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2024},
     doi = {10.7155/jgaa.v28i2.2995},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2995/}
}
TY  - JOUR
AU  - Cornelius Brand
AU  - Robert Ganian
AU  - Sebastian Röder
AU  - Florian Schager
TI  - Fixed-Parameter Algorithms for Computing Bend-Restricted RAC Drawings of Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 131
EP  - 150
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2995/
DO  - 10.7155/jgaa.v28i2.2995
LA  - en
ID  - JGAA_2024_28_2_a6
ER  - 
%0 Journal Article
%A Cornelius Brand
%A Robert Ganian
%A Sebastian Röder
%A Florian Schager
%T Fixed-Parameter Algorithms for Computing Bend-Restricted RAC Drawings of Graphs
%J Journal of Graph Algorithms and Applications
%D 2024
%P 131-150
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2995/
%R 10.7155/jgaa.v28i2.2995
%G en
%F JGAA_2024_28_2_a6
Cornelius Brand; Robert Ganian; Sebastian Röder; Florian Schager. Fixed-Parameter Algorithms for Computing Bend-Restricted RAC Drawings of Graphs. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023
					, Tome 28 (2024) no. 2, pp. 131-150. doi : 10.7155/jgaa.v28i2.2995. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2995/

Cité par Sources :