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)

Created from the Publication Database of the Vienna University of Technology.