Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Nöllenburg, B. Klemz, R. Prutkin:
"Recognizing Weighted Disk Contact Graphs";
Vortrag: Graph Drawing and Network Visualization (GD´15),
Los Angeles, USA;
24.09.2015
- 26.09.2015; in: "Graph Drawing and Network Visualization (GD'15)",
E. Di Giacomo, A. Lubiw (Hrg.);
Springer,
LNCS 9411
(2015),
ISBN: 978-3-319-27260-3;
S. 433
- 446.
Kurzfassung englisch:
Disk contact representations realize graphs by mapping vertices bijectively to interior-disjoint disks in the plane such that two disks touch each other if and only if the corresponding vertices are adjacent in the graph. Deciding whether a vertex-weighted planar graph can be realized such that the disks´ radii coincide with the vertex weights is known to be NP-hard. In this work, we reduce the gap between hardness and tractability by analyzing the problem for special graph classes. We show that it remains NP-hard for outerplanar graphs with unit weights and for stars with arbitrary weights, strengthening the previous hardness results. On the positive side, we present constructive linear-time recognition algorithms for caterpillars with unit weights and for embedded stars with arbitrary weights.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-319-27261-0
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.