Talks and Poster Presentations (with Proceedings-Entry):
T. Hamm, F. Klute, I. Parada:
"Extending to 1-plane drawings";
Talk: Spanish Meeting on Computational Geometry,
Girona;
2019-07-01
- 2019-07-03; in: "Abstracts of the XVIII Spanish Meeting on Computational Geometry",
(2019),
30 pages.
English abstract:
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.
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_284640.pdf
Created from the Publication Database of the Vienna University of Technology.