Geodesic
Parameterized Algorithms for Queue Layouts
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020 , Tome 26 (2022) no. 3, pp. 335-352.

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

An $h$-queue layout of a graph $G$ consists of a linear order of its vertices and a partition of its edges into $h$ sets, called queues, such that no two independent edges of the same queue nest. The minimum $h$ such that $G$ admits an $h$-queue layout is the queue number of $G$. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph $G$ has queue number $1$ and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of $G$. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary $h$.
DOI : 10.7155/jgaa.00597
Keywords: graph drawing, queue layouts, parameterized complexity 
@article{JGAA_2022_26_3_a3,
     author = {Sujoy Bhore and Robert Ganian and Fabrizio Montecchiani and Martin N\"ollenburg},
     title = {Parameterized {Algorithms} for {Queue} {Layouts}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {335--352},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2022},
     doi = {10.7155/jgaa.00597},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00597/}
}
TY  - JOUR
AU  - Sujoy Bhore
AU  - Robert Ganian
AU  - Fabrizio Montecchiani
AU  - Martin Nöllenburg
TI  - Parameterized Algorithms for Queue Layouts
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 335
EP  - 352
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00597/
DO  - 10.7155/jgaa.00597
LA  - en
ID  - JGAA_2022_26_3_a3
ER  - 
%0 Journal Article
%A Sujoy Bhore
%A Robert Ganian
%A Fabrizio Montecchiani
%A Martin Nöllenburg
%T Parameterized Algorithms for Queue Layouts
%J Journal of Graph Algorithms and Applications
%D 2022
%P 335-352
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00597/
%R 10.7155/jgaa.00597
%G en
%F JGAA_2022_26_3_a3
Sujoy Bhore; Robert Ganian; Fabrizio Montecchiani; Martin Nöllenburg. Parameterized Algorithms for Queue Layouts. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020
					, Tome 26 (2022) no. 3, pp. 335-352. doi : 10.7155/jgaa.00597. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00597/

Cité par Sources :