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
Date Issued
2011
Publisher
Publisher place
Berlin
Published in
Proc. 19th International Symposium on Graph Drawing
ISBN of the book
978-3-642-25877-0
Total of pages
12
Series title/Series vol.
Lecture Notes in Computer Science; 7034
Start page
391
End page
402
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
| Event name | Event place |
Eindhoven, Netherlands | |
Available on Infoscience
December 19, 2011
Use this identifier to reference this record