Recognition of Unit Disk Graphs for Caterpillars, Embedded Trees, and Outerplanar Graphs

Unit disk graphs are graphs that have a unit disk intersection representation (UDR). In the recognition problem the objective is to decide whether a given graph is a unit disk graph, which is known to be NP-hard, even for planar graphs. In this work, we show that the recognition of unit disk graphs remains NP-hard for outerplanar graphs and for embedded trees. We also show that given a caterpillar graph, we can decide in linear time whether it is a unit disk graph.