Geodesic
Stack and Queue Layouts via Layered Separators
Journal of Graph Algorithms and Applications, Special Issue on Graph Drawing Beyond Planarity , Tome 22 (2018) no. 1, pp. 89-99.

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

It is known that every proper minor-closed class of graphs has bounded stack-number (a.k.a. book thickness and page number). While this includes notable graph families such as planar graphs and graphs of bounded genus, many other graph families are not closed under taking minors. For fixed $g$ and $k$, we show that every $n$-vertex graph that can be embedded on a surface of genus $g$ with at most $k$ crossings per edge has stack-number $\mathcal{O}(\log n)$; this includes $k$-planar graphs. The previously best known bound for the stack-number of these families was $\mathcal{O}(\sqrt{n})$, except in the case of $1$-planar graphs. Analogous results are proved for map graphs that can be embedded on a surface of fixed genus. None of these families is closed under taking minors. The main ingredient in the proof of these results is a construction proving that $n$-vertex graphs that admit constant layered separators have $\mathcal{O}(\log n)$ stack-number. 
@article{JGAA_2018_22_1_a5,
     author = {Vida Dujmovi\'c and Fabrizio Frati},
     title = {Stack and {Queue} {Layouts} via {Layered} {Separators}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {89--99},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2018},
     doi = {10.7155/jgaa.00454},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00454/}
}
TY  - JOUR
AU  - Vida Dujmović
AU  - Fabrizio Frati
TI  - Stack and Queue Layouts via Layered Separators
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 89
EP  - 99
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00454/
DO  - 10.7155/jgaa.00454
LA  - en
ID  - JGAA_2018_22_1_a5
ER  - 
%0 Journal Article
%A Vida Dujmović
%A Fabrizio Frati
%T Stack and Queue Layouts via Layered Separators
%J Journal of Graph Algorithms and Applications
%D 2018
%P 89-99
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00454/
%R 10.7155/jgaa.00454
%G en
%F JGAA_2018_22_1_a5
Vida Dujmović; Fabrizio Frati. Stack and Queue Layouts via Layered Separators. Journal of Graph Algorithms and Applications, 
							Special Issue on Graph Drawing Beyond Planarity
					, Tome 22 (2018) no. 1, pp. 89-99. doi : 10.7155/jgaa.00454. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00454/

Cité par Sources :