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),
- 2021-09-17; in: "International Symposium on Graph Drawing and Network Visualization-GD2021",
LNCS / Springer,
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)
Created from the Publication Database of the Vienna University of Technology.