On the Page Number of Upward Planar Directed Acyclic Graphs
Vol. 17, no. 3, pp. 221-244, 2013. Regular paper.
Abstract 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.
Submitted: January 2013.
Accepted: March 2013.
Final: April 2013.
Published: May 2013.
Communicated by Giuseppe Liotta
article (PDF)