Talks and Poster Presentations (with Proceedings-Entry):

S. Bhore, G. Da Lozzo, F. Montecchiani, M. Nöllenburg:
"On the Upward Book Thickness Problem: Combinatorial and Complexity Results";
Talk: International Symposium on Graph Drawing and Network Visualization (GD), Tübingen, Germany; 2021-09-14 - 2021-09-17; in: "International Symposium on Graph Drawing and Network Visualization-GD2021", LNCS / Springer, 12868 (2021), ISBN: 978-3-030-92930-5; 242 - 256.

English abstract:
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 st-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.

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Created from the Publication Database of the Vienna University of Technology.