Geodesic
On the Page Number of Upward Planar Directed Acyclic Graphs
Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 3, pp. 221-244.

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

In this paper we study the page number of upward planar directed acyclic graphs. We prove that: (1) the page number of any n-vertex upward planar triangulation G whose every maximal 4-connected component has page number k is at most min{O(klogn),O(2k)}; (2) every upward planar triangulation G with o(n/logn) diameter has o(n) page number; and (3) every upward planar triangulation has a vertex ordering with o(n) page number if and only if every upward planar triangulation whose maximum degree is O(√n) does.
DOI : 10.7155/jgaa.00292
Keywords: Book Embedding, Page Number, Directed Acyclic Graphs, Upward Planarity 
@article{JGAA_2013_17_3_a3,
     author = {Fabrizio Frati and Radoslav Fulek and Andres Ruiz-Vargas},
     title = {On the {Page} {Number} of {Upward} {Planar} {Directed} {Acyclic} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {221--244},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2013},
     doi = {10.7155/jgaa.00292},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00292/}
}
TY  - JOUR
AU  - Fabrizio Frati
AU  - Radoslav Fulek
AU  - Andres Ruiz-Vargas
TI  - On the Page Number of Upward Planar Directed Acyclic Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 221
EP  - 244
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00292/
DO  - 10.7155/jgaa.00292
LA  - en
ID  - JGAA_2013_17_3_a3
ER  - 
%0 Journal Article
%A Fabrizio Frati
%A Radoslav Fulek
%A Andres Ruiz-Vargas
%T On the Page Number of Upward Planar Directed Acyclic Graphs
%J Journal of Graph Algorithms and Applications
%D 2013
%P 221-244
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00292/
%R 10.7155/jgaa.00292
%G en
%F JGAA_2013_17_3_a3
Fabrizio Frati; Radoslav Fulek; Andres Ruiz-Vargas. On the Page Number of Upward Planar Directed Acyclic Graphs. Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 3, pp. 221-244. doi : 10.7155/jgaa.00292. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00292/

Cité par Sources :