Paper

{
  "raw_xml": "<entry>\n    <id>http://arxiv.org/abs/2603.17128v1</id>\n    <title>Upward Book Embeddings of Partitioned Digraphs</title>\n    <updated>2026-03-17T20:42:16Z</updated>\n    <link href='https://arxiv.org/abs/2603.17128v1' rel='alternate' type='text/html'/>\n    <link href='https://arxiv.org/pdf/2603.17128v1' rel='related' title='pdf' type='application/pdf'/>\n    <summary>In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in which the vertices must appear along the spine in a topological order and the edges are partitioned into pages, so that no two edges in the same page cross. For a partitioned digraph $G=(V,\\bigcup^k_{i=1} E_i)$, that is, a digraph whose edge set is partitioned into $k$ subsets, an upward book embedding is required to assign edges to pages as prescribed by the given partition. In a companion paper, Heath and Pemmaraju [SIAM J. Comput 28(5), 1999] proved that the problem of testing the existence of an upward book embedding of a partitioned digraph is linear-time solvable for $k=1$ and recently Akitaya, Demaine, Hesterberg, and Liu [GD, 2017] have shown the problem NP-complete for $k\\geq 3$. In this paper, we study upward book embeddings of partitioned digraphs and focus on the unsolved case $k=2$. Our first main result is a novel characterization of the upward embeddings that support an upward book embedding in two pages. We exploit this characterization in several ways, and obtain a rich picture of the complexity landscape of the problem. First, we show that the problem remains NP-complete when $k=2$, thus closing the complexity gap for the problem. Second, we show that, for an $n$-vertex partitioned digraph $G$ with a prescribed planar embedding, the existence of an upward book embedding of $G$ that respects the given planar embedding can be tested in $O(n \\log^3 n)$ time. Finally, leveraging the SPQ(R)-tree decomposition of biconnected graphs into triconnected components, we present a cubic-time testing algorithm for biconnected directed partial $2$-trees.</summary>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.DS'/>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.CG'/>\n    <published>2026-03-17T20:42:16Z</published>\n    <arxiv:comment>Appears in SoCG '26</arxiv:comment>\n    <arxiv:primary_category term='cs.DS'/>\n    <author>\n      <name>Giordano Da Lozzo</name>\n    </author>\n    <author>\n      <name>Fabrizio Frati</name>\n    </author>\n    <author>\n      <name>Ignaz Rutter</name>\n    </author>\n  </entry>"
}