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)
http://dx.doi.org/10.1007/978-3-030-92931-2_18
Created from the Publication Database of the Vienna University of Technology.