[Back]


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.