2026-08-18T11:50:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10417 2024-03-06T10:45:56Z ddc:004 open_access

Upward Book Embeddings of st-Graphs Binucci, Carla Da Lozzo, Giordano Di Giacomo, Emilio Didimo, Walter Mchedlidze, Tamara Patrignani, Maurizio Upward Book Embeddings st-Graphs SPQR-trees Branchwidth Sphere-cut Decomposition We study k-page upward book embeddings (kUBEs) of st-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on k pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a kUBE is NP-complete for k >= 3. A hardness result for this problem was previously known only for k = 6 [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on k=2. On the algorithmic side, we present polynomial-time algorithms for testing the existence of 2UBEs of planar st-graphs with branchwidth b and of plane st-graphs whose faces have a special structure. These algorithms run in O(f(b)* n+n^3) time and O(n) time, respectively, where f is a singly-exponential function on b. Moreover, on the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving 2UBE. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Carla Binucci and Giordano Da Lozzo and Emilio Di Giacomo and Walter Didimo and Tamara Mchedlidze and Maurizio Patrignani 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.13 urn:nbn:de:0030-drops-104170 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.13 eng https://creativecommons.org/licenses/by/3.0/legalcode