Talks and Poster Presentations (with Proceedings-Entry):
S. Bhore, M. Löffler, S. Nickel, M. Nöllenburg:
"Unit Disk Representations of Embedded Trees, Outerplanar and Multi-legged Graphs";
Talk: International Symposium on Graph Drawing and Network Visualization (GD),
Tübingen, Germany;
2021-09-14
- 2021-09-17; in: "International Symposium on Graph Drawing and Network Visualization-GD2021",
LNCS / Springer,
12868
(2021),
ISBN: 978-3-030-92930-5;
304
- 317.
English abstract:
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-92931-2_22
Created from the Publication Database of the Vienna University of Technology.