Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Chiu, J. Cleve, M. Nöllenburg:
"Recognizing embedded caterpillars with weak unit disk contact representations is NP-hard";
Vortrag: EuroCG,
Utrecht, Niederlande;
18.03.2019
- 20.03.2019; in: "Extended abstract of EuroCG 2019",
(2019),
S. 1
- 9.
Kurzfassung englisch:
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.
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_284607.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.