Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
S. Bhore, M. Löffler, S. Nickel, M. Nöllenburg:
"Unit Disk Representations of Embedded Trees, Outerplanar and Multi-legged Graphs";
Vortrag: International Symposium on Graph Drawing and Network Visualization (GD),
Tübingen, Germany;
14.09.2021
- 17.09.2021; in: "International Symposium on Graph Drawing and Network Visualization-GD2021",
LNCS / Springer,
12868
(2021),
ISBN: 978-3-030-92930-5;
S. 304
- 317.
Kurzfassung englisch:
A unit disk intersection representation (UDR) of a graph G
represents each vertex of G as a unit disk in the plane, such that two
disks intersect if and only if their vertices are adjacent in G. A UDR with
interior-disjoint disks is called a unit disk contact representation (UDC).
We prove that it is NP-hard to decide if an outerplanar graph or an
embedded tree admits a UDR. We further provide a linear-time decidable
characterization of caterpillar graphs that admit a UDR. Finally we show
that it can be decided in linear time if a lobster graph admits a weak
UDC, which permits intersections between disks of non-adjacent vertices.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-92931-2_22
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.