Can I read On the Upward Book Thickness Problem: Combinatorial and Complexity Results on EtoBox?

On the Upward Book Thickness Problem: Combinatorial and Complexity Results by Bhore, Sujoy; Da Lozzo, Giordano; Montecchiani, Fabrizio; Nöllenburg, Martin is a scholarly article available to read on EtoBox.

What is On the Upward Book Thickness Problem: Combinatorial and Complexity Results about?

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 \ge 3$. We show that the problem, for any $k \ge 5$, remains NP-hard for graphs whose domination number is $O(k)$, but it is FPT in the vertex cover number.

Author

Bhore, Sujoy; Da Lozzo, Giordano; Montecchiani, Fabrizio; Nöllenburg, Martin

Published

2021

Language

EN