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.

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.

http://dx.doi.org/10.1007/978-3-030-92931-2_22

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