2021/08/27 by Sujoy Bhore, Giordano Da Lozzo, Bhore, Sujoy +5 · 3 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2108.12327
openalex publication_date 2021/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are at-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness k is NP-hard for any fixed k ≥ 3. We show that the problem, for any k ≥ 5, remains NP-hard for graphs whose domination number is O(k), but it is FPT in the vertex cover number.