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.
Bhore, S., Da Lozzo, G., Montecchiani, F., & Nollenburg, M. (2021). On the Upward Book Thickness Problem: Combinatorial and Complexity Results. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.242-256). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-92931-2_18].
Titolo: | On the Upward Book Thickness Problem: Combinatorial and Complexity Results | |
Autori: | ||
Data di pubblicazione: | 2021 | |
Serie: | ||
Citazione: | Bhore, S., Da Lozzo, G., Montecchiani, F., & Nollenburg, M. (2021). On the Upward Book Thickness Problem: Combinatorial and Complexity Results. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.242-256). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-92931-2_18]. | |
Handle: | http://hdl.handle.net/11590/404544 | |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |