On the Page Number of Upward Planar Directed Acyclic Graphs

Frati, Fabrzio and Fulek, Radoslav and Ruiz-Vargas, Andres J. (2012) On the Page Number of Upward Planar Directed Acyclic Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011 , pp. 391-402(Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_37).

Full text not available from this repository.

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(k log n), O(2k )}; (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(√n) does.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_37
Classifications: G Algorithms and Complexity > G.490 Embeddings
P Styles > P.840 Upward
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1272

Actions (login required)

View Item View Item