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";
- 2019-03-20; in: "Extended abstract of EuroCG 2019",
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:
Created from the Publication Database of the Vienna University of Technology.