Loading...
conference paper
On the Page Number of Upward Planar Directed Acyclic Graphs
2011
Proc. 19th International Symposium on Graph Drawing
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.
Type
conference paper
Web of Science ID
WOS:000307210800036
Authors
Publication date
2011
Publisher
Published in
Proc. 19th International Symposium on Graph Drawing
ISBN of the book
978-3-642-25877-0
Publisher place
Berlin
Total of pages
12
Series title/Series vol.
Lecture Notes in Computer Science; 7034
Start page
391
End page
402
Peer reviewed
REVIEWED
EPFL units
Event name | Event place |
Eindhoven, Netherlands | |
Available on Infoscience
December 19, 2011
Use this identifier to reference this record