Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
T. Hamm, F. Klute, I. Parada:
"Extending to 1-plane drawings";
Vortrag: Spanish Meeting on Computational Geometry,
Girona;
01.07.2019
- 03.07.2019; in: "Abstracts of the XVIII Spanish Meeting on Computational Geometry",
(2019),
30 S.
Kurzfassung englisch:
We study the problem of extending a connected
(1-)plane drawing of a graph G with a maximum set
of edges M0 chosen from a given set of edges M of the
complement graph of G. It turns out the problem is
NP-hard already for the case of the initial drawing be-
ing plane and orthogonal. On the positive side we give
an FPT-algorithm in k for the case of adding k edges
and M being the set of all edges in the complement
of G.
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_284640.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.