Geodesic
Two Results on Layered Pathwidth and Linear Layouts
Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 43-57.

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

Layered pathwidth is a new graph parameter studied by Bannister et al. (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts. Our first result shows that, for any graph $G$, the stack number of $G$ is at most four times the layered pathwidth of $G$. Our second result shows that any graph $G$ with track number at most three has layered pathwidth at most four. The first result complements a result of Dujmović and Frati (2018) relating layered treewidth and stack number. The second result solves an open problem posed by Bannister et al. (2015).
DOI : 10.7155/jgaa.00549
Keywords: layered pathwidth, stack number, page number, track number 
@article{JGAA_2021_25_1_a2,
     author = {Vida Dujmovi\'c and Pat Morin and C\'eline Yelle},
     title = {Two {Results} on {Layered} {Pathwidth} and {Linear} {Layouts}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {43--57},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2021},
     doi = {10.7155/jgaa.00549},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00549/}
}
TY  - JOUR
AU  - Vida Dujmović
AU  - Pat Morin
AU  - Céline Yelle
TI  - Two Results on Layered Pathwidth and Linear Layouts
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 43
EP  - 57
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00549/
DO  - 10.7155/jgaa.00549
LA  - en
ID  - JGAA_2021_25_1_a2
ER  - 
%0 Journal Article
%A Vida Dujmović
%A Pat Morin
%A Céline Yelle
%T Two Results on Layered Pathwidth and Linear Layouts
%J Journal of Graph Algorithms and Applications
%D 2021
%P 43-57
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00549/
%R 10.7155/jgaa.00549
%G en
%F JGAA_2021_25_1_a2
Vida Dujmović; Pat Morin; Céline Yelle. Two Results on Layered Pathwidth and Linear Layouts. Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 43-57. doi : 10.7155/jgaa.00549. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00549/

Cité par Sources :