Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
S. Bhore, G. Da Lozzo, F. Montecchiani, M. Nöllenburg:
"On the Upward Book Thickness Problem: Combinatorial and Complexity Results";
Vortrag: International Symposium on Graph Drawing and Network Visualization (GD),
Tübingen, Germany;
14.09.2021
- 17.09.2021; in: "International Symposium on Graph Drawing and Network Visualization-GD2021",
LNCS / Springer,
12868
(2021),
ISBN: 978-3-030-92930-5;
S. 242
- 256.
Kurzfassung englisch:
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.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-92931-2_18
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.