On the Page Number of Upward Planar Directed Acyclic Graphs

In this paper we study the page number of upward planar directed acyclic graphs. We prove that: (I) 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(k log n), O(2(k))1; (2) every upward planar triangulation G with o(n/log n) 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(root n) does.


Published in:
Proc. 19th International Symposium on Graph Drawing, 391-402
Presented at:
19th International Symposium on Graph Drawing, Eindhoven, Netherlands
Year:
2011
Publisher:
Berlin, Springer-Verlag Berlin
ISBN:
978-3-642-25877-0
Laboratories:




 Record created 2011-12-19, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)