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, Eindhoven, The Netherlands , pp. 391-402 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_37).

Full text not available from this repository.


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
ID Code:1272

Repository Staff Only: item control page


Alzohairi, M., Rival, I.: Series-Parallel Planar Ordered Sets Have Pagenumber Two. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 11–24. Springer, Heidelberg (1997)

Buss, J.F., Shor, P.W.: On the pagenumber of planar graphs. In: Symposium on Theory of Computing (STOC 1984), pp. 98–100. ACM (1984)

Cerný, J.: Coloring circle graphs. Elec. Notes Discr. Math. 29, 457–461 (2007)

Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: A layout problem with applications to VLSI design. SIAM J. Alg. Discr. Meth. 8, 33–58 (1987)

Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theor. Comp. Sci. 61, 175–198 (1988)

Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Book embeddability of series- parallel digraphs. Algorithmica 45(4), 531–547 (2006)

Enomoto, H., Nakamigawa, T., Ota, K.: On the pagenumber of complete bipartite graphs. J. Comb. Th. Ser. B 71(1), 111–120 (1997)

Ganley, J.L., Heath, L.S.: The pagenumber of k-trees is O(k). Discr. Appl. Math. 109(3), 215–221 (2001)

Heath, L.S.: Embedding planar graphs in seven pages. In: Foundations of Computer Science (FOCS 1984), pp. 74–83. IEEE (1984)

Heath, L.S., Istrail, S.: The pagenumber of genus g graphs is O(g). J. ACM 39(3), 479–501 (1992)

Heath, L.S., Leighton, F.T., Rosenberg, A.L.: Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discr. Math. 5(3), 398–412 (1992)

Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of posets. SIAM J. Discr. Math. 10(4), 599–625 (1997)

Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of directed acyclic graphs: Part II. SIAM J. Computing 28(5), 1588–1626 (1999)

Heath, L.S., Pemmaraju, S.V., Trenk, A.N.: Stack and queue layouts of directed acyclic graphs: Part I. SIAM J. Computing 28(4), 1510–1539 (1999)

Kainen, P.C.: Thickness and coarseness of graphs. Abh. Math. Sem. Univ. Hamburg 39, 88–95 (1973)

Kostochka, A.V., Kratochvíl, J.: Covering and coloring polygon-circle graphs. Discr. Math. 163(1-3), 299–305 (1997)

Malitz, S.M.: Genus g graphs have pagenumber O(√g). J. Algorithms 17(1), 85–109 (1994)

18. Malitz, S.M.: Graphs with e edges have pagenumber O(√e). J. Algorithms 17(1), 71–84 (1994)

Ollmann, L.T.: On the book thicknesses of various graphs. In: Hoffman, F., Levow, R.B., Thomas, R.S.D. (eds.) Southeastern Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. VIII, p. 459 (1973)

Rosenberg: The Diogenes approach to testable fault-tolerant arrays of processors. IEEE Trans. Comp. C-32, 902–910 (1983)

Tarjan, R.E.: Sorting using networks of queues and stacks. J. ACM 19(2), 341–346 (1972)

Yannakakis, M.: Embedding planar graphs in four pages. J. Comp. Syst. Sci. 38(1), 36–67 (1989)