2026-07-23T00:29:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24995 2026-02-09T07:52:38Z ddc:004 open_access

The Page Number of Monotone Directed Acyclic Outerplanar Graphs Is Four or Five Alam, Jawaherul Md. Bekos, Michael A. Gronemann, Martin Kaufmann, Michael Book embeddings page number directed outerplanar graphs A k-page book embedding of a directed acyclic graph consists of a topological order of its vertices and a k-coloring of its edges, such that no two edges of the same color cross, that is, their endpoints do not alternate in the order. The minimum value of k for which such an embedding exists is referred to as the page number of the graph. In contrast to general directed acyclic planar graphs, which may have unbounded page number [SIAM J. Comput. 28(5), 1999], it was recently shown that directed acyclic outerplanar graphs have bounded page number. In particular, Jungeblut, Merker and Ueckerdt provided an upper bound of 24,776 on their page number [FOCS 2023: 1937-1952]. In this work, we focus on so-called monotone directed acyclic outerplanar graphs. Starting from a single edge, these graphs are constructed by iteratively connecting a new vertex to the endpoints of an existing edge on the outer face using either two incoming or two outgoing edges incident to it. These graphs have twist-number 4 [GD 2023: 135-151] (i.e., they admit a topological order in which no more than four edges pairwise cross), a property, which was leveraged by Jungeblut, Merker and Ueckerdt to show that their page number is at most 128. We lower this upper bound to 5 and we also provide a lower bound of 4. A notable consequence of our result is a significant improvement of the upper bound on the page number of general directed outerplanar graphs from 24,776 to 1,160. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jawaherul Md. Alam and Michael A. Bekos and Martin Gronemann and Michael Kaufmann 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.9 urn:nbn:de:0030-drops-249952 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode