Talks and Poster Presentations (with Proceedings-Entry):
M. Chiu, J. Cleve, M. Nöllenburg:
"Recognizing embedded caterpillars with weak unit disk contact representations is NP-hard";
Talk: EuroCG,
Utrecht, Niederlande;
2019-03-18
- 2019-03-20; in: "Extended abstract of EuroCG 2019",
(2019),
1
- 9.
English abstract:
Weak unit disk contact graphs are graphs that admit a representation of the nodes as a collection
of internally disjoint unit disks whose boundaries touch if there is an edge between the
corresponding nodes. We provide a gadget-based reduction to show that recognizing embedded
caterpillars that admit a weak unit disk contact representation is NP-hard.
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_284607.pdf
Created from the Publication Database of the Vienna University of Technology.