On the Page Number of Upward Planar Directed Acyclic Graphs

Authors

  • Fabrizio Frati
  • Radoslav Fulek
  • Andres Ruiz-Vargas

DOI:

https://doi.org/10.7155/jgaa.00292

Keywords:

Book Embedding , Page Number , Directed Acyclic Graphs , Upward Planarity

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.

Downloads

Download data is not yet available.

Downloads

Published

2013-03-01

How to Cite

Frati, F., Fulek, R., & Ruiz-Vargas, A. (2013). On the Page Number of Upward Planar Directed Acyclic Graphs. Journal of Graph Algorithms and Applications, 17(3), 221–244. https://doi.org/10.7155/jgaa.00292

Issue

Section

Articles

Categories