11institutetext: Indian Institute of Science Education and Research, Bhopal,
India
11email<EMAIL_ADDRESS>22institutetext: Department of Computing and
Information Sciences, Utrecht University
22email<EMAIL_ADDRESS>33institutetext: Algorithms and Complexity Group, TU
Wien, Vienna, Austria
33email<EMAIL_ADDRESS>
#  Unit Disk Representations of Embedded Trees, Outerplanar and Multi-Legged
Graphs

Sujoy Bhore 11 0000-0003-0104-1659 Maarten Löffler 22 Soeren Nickel 33
0000-0001-5161-3841 Martin Nöllenburg 33 0000-0003-0454-3937

###### 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
-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.

##  1 Introduction

The representation of graphs as contacts or intersections of disks has been a
major topic of investigation in geometric graph theory and graph drawing. The
famous circle packing theorem states that every planar graph has a contact
representation by touching disks (of various size) and vice versa [13]. Since
then, a large body of research has been devoted to the representation of
planar graphs as contacts or intersections of various kinds of geometric
objects [4, 5, 8, 9]. In this paper, we are interested in unit-radius disks. A
set of unit disks in $\mathbb{R}^{2}$ is a _unit disk intersection
representation_ (UDR) of a graph $G=(V,E)$, if there is a bijection between
$V$ and the set of unit disks such that two disks intersect if and only if
they are adjacent in $G$. _Unit disk graphs_ are graphs that admit a UDR.
_Unit disk contact graphs_ (also known as _penny graphs_) are the subfamily of
unit disk graphs that have a UDR with interior-disjoint disks, which is thus
called a _unit disk contact representation_ (UDC). This can be relaxed to
_weak_ UDCs, which permit contact between non-adjacent disks; see Fig. 1 for
examples.

(a) Outerplanar graph

(b) Caterpillar graph

(c) Lobster graph

Figure 1:  We investigate specific contact and intersection graphs of unit
disks. In a UDR (a-b) disks are allowed to overlap, and contact of two disks
implies an edge between their vertices. In a weak UDC the disks are interior
disjoint, but contact between non-adjacent disks is allowed. The disks of
backbone vertices are colored grey (b-c).

The recognition problem, where the objective is to decide whether a given
graph admits a UDR, has a rich history [1, 2, 10, 11]. Breu and Kirkpatrick
[3] proved that it is NP-hard to decide whether a graph $G$ admits a UDR or a
UDC, even for planar graphs. Klemz et al. [12] showed that recognizing
outerplanar unit disk contact graphs is already NP-hard, but it is decidable
in linear time for caterpillars, i.e., trees whose internal vertices form a
path (see Fig. 1).

Recognition with a fixed embedding is an important variant of the recognition
problem. Given a plane graph $G$, the objective in this problem is to decide
whether $G$ admits a UDC in the plane that preserves the cyclic order of the
neighbors at each vertex. Some recent works investigated the recognition
problem of UDCs with/without fixed embedding, and narrowed down the precise
boundary between hardness and tractability; see [1, 6, 7, 12]. A remaining
open question is to settle the complexity of recognizing non-embedded trees
that admit a UDC. Some of these works focused on _weak_ UDCs, where disks of
non-adjacent vertices may touch. In this model, the recognition of non-
embedded trees that admit a weak UDC is -hard [7]. We summarize the results on
weak UDCs in Table 1.

While several results of the past years have shed light into the recognition
complexity gap for UDCs, not much is known in this regard for the more general
class of UDRs since the -hardness for planar graphs from 1998 [3].

##### Our Contribution.

We investigate the unit disk graph recognition problem for subclasses of
planar graphs. We show that recognizing unit disk graphs remains NP-hard for
non-embedded outerplanar graphs (see Fig. 1) – strengthening the previous
hardness result for planar graphs [3] – and for embedded trees (Section 3).
This line of research aims to extend earlier investigations [1, 6, 7] of UDCs
to the UDR model and builds in particular on the work of Bowen et al. [1].

On the positive side, we provide a linear-time algorithm to recognize
caterpillar graphs (see Fig. 1) that admit a UDR (Section 4). In Section 5, we
return to the problem of recognizing unit disk contact graphs and extend the
tractability boundary for non-embedded graphs. While it was known that a weak
UDC for caterpillar graphs can be constructed in linear time (if one exists),
but the same recognition problem is -hard for trees [7], we prove that we can
decide in linear time if a lobster graph admits a weak UDC on the triangular
grid, where a _lobster_ is a tree whose internal vertices form a caterpillar
(see Fig. 1). Table 1 summarizes our results and remaining open problems.
Proofs and details of results marked with a star ($\star$) can be found in the
appendix.

graph class | weak UDC | UDR
---|---|---
| non-embedded | embedded | non-embedded | embedded
planar |  $\uparrow$ -hard |  $\uparrow$ -hard |  -hard [3] |  $\uparrow$ -hard
outerplanar |  $\uparrow$ -hard |  $\uparrow$ -hard |  -hard (Thm.3.1) |  $\uparrow$ -hard
trees |  -hard [7] |  $\uparrow$ -hard | open |  -hard (Thm.3.2)
lobsters |  $O(n)$ (Thm.5.1) |  $\uparrow$ -hard | open | open
caterpillars |  $O(n)$ [7] |  -hard [6] |  $O(n)$ (Thm.4.1) | open
Table 1: State of the art, our results, and open problems on unit disk graph
recognition. Upward arrows indicate, that a result follows from the one below.

##  2 Preliminaries

A graph $G=(V,E)$ with $V=\\{v_{1},\dots,v_{n}\\}$ is a unit disk graph if
there exists a set of closed unit disks $\mathcal{D}=\\{d_{1},\dots,d_{n}\\}$
and a bijective mapping $d\colon V\rightarrow\mathcal{D}$, s.t.,
$d(v_{i})=d_{i}$ and $v_{i}v_{j}\in E$ if and only if $d_{i}$ and $d_{j}$
intersect. We call $\mathcal{D}$ a _unit disk intersection representation_
(UDR) of $G$. If all disks in $\mathcal{D}$ are pairwise interior disjoint we
also call $\mathcal{D}$ a _unit disk contact representation_ (UDC) of $G$. A
graph is a _unit disk contact graph_ if it admits a UDC. A _weak_ UDC permits
contact between two disks $d_{i}$ and $d_{j}$, even if $v_{i}v_{j}\not\in
E$.111Note that weak UDRs, in contrast, are not interesting, since a complete
graph $K_{n}$ can easily be represented as a UDR and therefore every graph
admits a weak UDR. A _caterpillar_ graph $G$ is a tree, which yields a path,
when all leaves are removed. We call this path, the backbone $B_{G}$ of $G$.
Similarly a _lobster_ graph $G^{\prime}$ is a tree, which yields a caterpillar
graph $G^{\prime\prime}$, when all leaves are removed. The backbone of
$G^{\prime}$ is the backbone of $G^{\prime\prime}$. For each vertex $v$ of the
backbone, we denote the set of vertices that are reachable from $v$ on a path
that does not include any other backbone vertex, as the _descendants_ of $v$.

The set of disks $\mathcal{D}$ induces an embedding
$\mathcal{E}_{\mathcal{D}}(G)$ of $G$ by placing every vertex $v$ at the
center of $d(v)$ and linking neighboring vertices by straight-line edges. We
will therefore also use $v$ as the center of $d(v)$. We say that a UDR
$\mathcal{D}$ preserves the embedding of an embedded graph $G$ with embedding
$\mathcal{E}(G)$ if $\mathcal{E}_{\mathcal{D}}(G)=\mathcal{E}(G)$. Let $a,b,c$
be three points in $\mathbb{R}^{2}$. We use $\measuredangle abc$ to denote the
clockwise angle defined between the segments ${ab}$ and ${bc}$. We define the
angle $\measuredangle d_{i}d_{j}d_{k}$ as the clockwise angle $\measuredangle
v_{i}v_{j}v_{k}$ in $\mathcal{E}_{\mathcal{D}}(G)$.

##  3 -Hardness Results

(a) Auxiliary hexagonal grid structure with embedded incidence graph

(b) False variable $x$. The connected wire on the top left is in a true state
and therefore corresponds to the negated literal $\neg x$.

(c) Unsatisfied state (left) and one possible satisfied state (right) of the
clause gadget

(d) True variable $x$. The wire is in a false state. The dotted hexagon
indicates the overlap, if hexagons would have inconsistent states.

Figure 2:  Auxiliary structure details used by Bowen et al. [1]. All Figures
are recreations/adaptions from their paper. The incidence graph is embedded on
a hexagonal grid (a). The edges are short corridors in which the blue hexagons
are fitted, hinged at white vertices. Hexagons in the variable cycle (red
line, grey backdrop) have two states (b) and (d). The clause gadget (c)
requires one hexagon, which does not enter the junction.

In this section, we prove that recognizing unit disk graphs remains -hard for
non-embedded outerplanar graphs and for embedded trees. Our proofs apply the
generic machinery of Bowen et al. [1] to decide realizability of polygonal
linkages, which requires to construct gadgets that can model hexagons and
rhombi in a stable way. First we sketch the reduction of Bowen et al. (full
details in Appendices 0.A.1–0.A.3), then we describe our constructions of the
required stable structures with outerplanar (Section 3.1) and embedded tree
gadgets (Section 3.2).

Bowen et al. [1] proved that recognizing unit disk contact graphs is NP-hard
for embedded trees, via a reduction from planar 3-SAT, which uses an auxiliary
construction formulated as a realization of a polygonal linkage. A polygonal
linkage is a set of polygons, which are realizable if they can be placed in
the plane, s.t., predefined sets of points on the boundary of these polygons
are identified. Bowen et al. define a set of hexagons in a hexagonal tiling
(Fig. 2) with small gaps between them, which form a hexagonal grid, in which a
representation of the incidence graph of the planar 3-SAT instance is fitted.
Smaller hexagons are fitted into cycles in this grid, s.t., they admit only
two different realizations, see Fig. 2, and determine the state of neighboring
small hexagons, see Fig. 2. The cycles represent variables in a true or false
state. The states of the cycles are transmitted via chains of smaller hexagons
into the gaps. The vertex, where three such chains meet, contains a small
hexagon on a thin connection, which can only be realized if at least one
transmitted state is true, see Fig. 2. The polygonal linkage is realizable if
and only if the planar 3-SAT instance is satisfiable. For a detailed
description, we refer to Appendix 0.A and Bowen et al. [1]. The building
blocks of this reduction are hexagons of variable sizes and short segments.
Bowen et al. [1] approximate the hexagons by creating graphs, whose UDCs must
be within a constant (asymmetric) Hausdorff distance222Recall that the
asymmetric Hausdorff distance from a set $A$ to a set $B$ in a metric space
with metric $d$ is defined as $d_{H}(A,B)=\sup_{a\in A}\inf_{b\in B}d(a,b)$.
of a hexagon and the segments similarly by providing graphs, whose UDCs must
be within a constant (asymmetric) Hausdorff distance of long thin rhombi. We
extend their notion of $\lambda$-stable approximations to UDRs.

###### Definition 1

A graph $G$ is a $\lambda$-stable approximation of a region $P$ in the plane
if, in every UDR of $G$, there exists a congruence transformation
$f:\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$ such that the union $U$ of all
unit disks in the UDR has an asymmetric Hausdorff distance
$d_{H}(f(P),U)\leq\lambda$.

###  3.1 Non-embedded Outerplanar Graphs

We prove that recognition of unit disk graphs is hard for non-embedded
outerplanar graphs by providing outerplanar graphs $G^{H}_{k}$ and
$G^{R}_{k}$, which are $7$-stable approximations of a hexagon of side length
$2k-1$ and a rhombus of width $2k+6$, respectively. Then, the -hardness
follows immediately from the construction of Bowen et al. [1] sketched above.
To obtain the $7$-stable approximations we present two graphs, which enforce
local bends in one direction of at least $\pi$ and $\frac{4\pi}{3}$ in any
UDR.

(a) Augmented $L_{17}$

(b) Corner connector

(c) UDR of (a)

(d) UDR of (b)

Figure 3:  Components for creating $\lambda$-stable approximations $G^{H}_{k}$
and $G^{R}_{k}$. Ladder $L_{17}$ (a) and its UDR (c), as well as a corner
connector (b) and its UDR (d). The corner connector connects two ladders
(lighter colored parts) and its actual parts have a darker color in (b). The
bends in the UDRs are required but exaggerated.

A _ladder_ $L_{k}$ (see Figs. 3 and 3) is a chain of pairwise connected
vertices $v_{i}$ and $v_{i}^{\prime}$, for $i=1,\dots,k$, also called the
outer and inner vertices of $L_{k}$, respectively. Additionally, so-called
extension neighbors, which are connected to only one outer vertex each, are
added on one side of the ladder, s.t., the outer vertices have alternating
degrees of four and five. Since the ladder consists of a chain of $C_{4}$’s,
these neighbors are forced to be placed all on the outside in an outerplanar
embedding. The minimal height of such a ladder is $2\sqrt{3}+2-\varepsilon$,
which is the height of the smallest bounding box of a tight packing of three
rows of unit disks minus an (arbitrarily) small constant $\varepsilon>0$.

The permission of overlap between adjacent disks allows for a placement of one
extension neighbor almost on top of its adjacent outer vertex, which leads to
an ever so slight inwards bend and, more importantly, any outwards bend is
impossible. In order to enforce an inward bend of at least $\frac{4\pi}{3}$,
we connect the last inner vertex $u_{j}^{1}$ of one ladder with the first
inner vertex $u_{1}^{2}$ of a second ladder and the last and first outer
vertex $v_{j}^{1}$/$v_{1}^{2}$ of the first and second ladder, respectively,
both with a vertex $v_{c}$, which has three attached extension neighbors, see
Fig. 3. This construction is called a _corner connector_. Since it is
impossible to place the disk of any extension neighbor of $v_{c}$ inside the
5-cycle $d(v_{j}^{1}),d(u_{j}^{1}),d(u_{1}^{2}),d(v_{1}^{2}),d(v_{c})$,
without overlapping at least two disks in the UDR, all extension neighbors are
still forced to the outside and therefore $\measuredangle
v_{j}^{1}v_{c}v_{1}^{2}>\frac{4\pi}{3}$, see Fig. 3.

Placing two ladders opposite each other and connecting them on one end with
three corner connectors as shown in Fig. 4, yields a $7$-stable approximation
$G^{R}_{k}$ of a thin rhombus. The following lemma is analogue to Lemma 10 in
[1].

######  Lemma 1 ($\star$)

For every positive integer $k$ the outerplanar graph $G^{R}_{k}$ in Fig. 4 is
a 7-stable approximation of a rhombus of width $2k+6$ and height
$6\sqrt{3}+2$.

######  Proof (Sketch)

The graph $G^{R}_{k}$ is made up of components, which make any bend to the
outside impossible, see Fig. 4. Since two ladders need to be overlap free, the
minimum height of the ladders guarantees that part of the boundary of the
union over all disks in the UDR of $G^{R}_{k}$ lies above and below the line
$\overline{c_{0}l_{0}}$, see Fig. 4. The largest vertical distance of the
rhombus to this line is $3\sqrt{3}+1\approx 6.196<7$.

(a) Maximal distance to $\overline{c_{0}l_{0}}$

(b) UDR on both sides of $\overline{c_{0}l_{0}}$

Figure 4: A $7$-stable approximation $G^{R}_{7}$ of a rhombus superimposed on
its UDR. The maximal distance of any point of the UDR to
$\overline{c_{0}l_{0}}$ is smaller or equal 7 (a) and at all points of
$\overline{c_{0}l_{0}}$ a part of the UDR lies above and below
$\overline{c_{0}l_{0}}$ (b). Both UDRs require a small inward bend to be valid
and hatched disks indicate almost overlapping placement of a red disk on a
blue disk, with a small shift to the outer side. Both inward bends and outward
shifts are omitted.

######  Lemma 2 ($\star$)

For every integer $k=6n+4,n\in\mathbb{N}$, the outerplanar graph $G^{H}_{k}$
in Fig. 5(a) is a $7$-stable approximation of a regular hexagon of side length
$2k-1$.

######  Proof (Sketch)

The $7$-stable approximation $G^{H}_{k}$ of a hexagon of side length $2k-1$
uses again ladders and corner connectors to trace the outline of the hexagon.
Then the inside of this construction is filled with a set of ladders until no
additional ladders can be added, see Fig. 5(a). Outwards bends are impossible
by construction of the ladders and corner connectors and inwards bends are
strongly limited since the interior of the hexagon is almost completely filled
with ladders. Since the amount of compression in a ladder is very limited,
this leaves only a constant amount of space on the inside of a UDR of
$G^{H}_{k}$.

###### Theorem 3.1

Recognizing unit disk graphs is -hard for outerplanar graphs.

###### Proof

This result follows from Lemmas 1 and 2 by using the polygonal linkage
reduction of Bowen et al. [1] (see also Appendix 0.A). Note that we can
emulate hinges exactly as in the original reduction.

(a) Combination of the ladder and corner connectors into $7$-stable
approximation $G^{H}_{k}$ of a hexagon superimposed on its UDR.

(b) A $7$-stable approximation tree $T^{H}_{k}$ of a hexagon superimposed on
its UDR.

Figure 5: 7-stable hexagon approximations. Hatched disks indicate almost
overlapping placement of disks. Necessary infinitesimal bends are omitted. The
bend directions of the inner components are indicated with gray arrows. The
approximated regular hexagon is indicated by the dashed green outlines.

###  3.2 Embedded Trees

By slightly adapting the construction of the outerplanar graphs of Section
3.1, we can prove that recognizing unit disk graphs is -hard for embedded
trees. The crucial observation is that we used the outerplanarity of
$G^{R}_{k}$ and $G^{H}_{k}$ exclusively to be able to build a tree-like
structure out of chains of $4$\- and $5$-cycles. We used this to force the
placement of leaf disks to a specific side of these chains in any UDR of
$G^{R}_{k}$ and $G^{H}_{k}$. As we are concerned with embedded trees in this
section, we can omit the inner vertices of the ladder, as the given embedding
puts the leaves on the desired side of the chains. This results in a tree. We
call a ladder without the inner vertices a _chain_.

We can now use a very similar construction idea as for $G^{R}_{k}$ and
$G^{H}_{k}$ above. We need to augment both gadgets with an additional chain in
order to retain the property, that no parts of these gadgets can be folded
onto themselves. The resulting trees $T^{R}_{k}$ and $T^{H}_{k}$ are shown in
Figs. 6 and 5(b). A more detailed description can be found in the proof of
Theorem 3.2 in Section 0.A.5.

######  Theorem 3.2 ($\star$)

Recognizing unit disk graphs is -hard for embedded trees.

(c) Maximal distance to $\overline{c_{0}l_{0}}$

(d) UDR on both sides of $\overline{c_{0}l_{0}}$

Figure 6:  A $7$-stable approximation $T^{R}_{k}$ of a long thin rhombus
superimposed on its UDR. The maximal distance of any point of the UDR to
$\overline{c_{0}l_{0}}$ is smaller or equal 7 (a) and at all points of
$\overline{c_{0}l_{0}}$ a part of the UDR lies above and below
$\overline{c_{0}l_{0}}$ (b). In both cases at any point along
$\overline{c_{0}l_{0}}$ at least one point on the boundary of the union of all
disks in a UDR of $T^{R}_{k}$ lies on or above $\overline{c_{0}l_{0}}$ and on
or below $\overline{c_{0}l_{0}}$.

##  4 Recognition Algorithm for Caterpillars

We propose a linear-time algorithm using similar ideas to Klemz et al. [12],
that recognizes if an input caterpillar graph $G=(V,E)$ admits a UDR or not;
it is constructive and provides a representation if one exists. However, we
need to address several new issues as we show that a larger class of graphs
admits a UDR compared to a UDC. Clearly, if $G$ contains a vertex of degree at
least $6$, then due to the unit disk packing property, it does not admit a
UDR. Hence, every realizable caterpillar must have maximum degree $\Delta\leq
5$. Moreover, it is easy to observe that all caterpillars with $\Delta\leq 4$
admit a UDC (and thus a UDR), as also noted by Klemz et al. [12]. Not every
caterpillar with $\Delta=5$, however, is realizable as UDR. We show that two
consecutive degree-$5$ vertices on $B_{G}$ cannot be realized. The following
lemma gives a sufficient condition for a “No” instance to be used in the
recognition algorithm. The proof of Lemma 3 is stated in Section 0.B.1.

######  Lemma 3 ($\star$)

If $B_{G}$ contains two adjacent degree $5$ vertices $u,v$, then it does not
admit a unit disk intersection representation.

###  4.1 The Algorithm

As a preprocessing step we augment all backbone vertices of degree $3$ or
lower with additional degree-$1$ neighbors, s.t., they have degree $4$.
Consider a chain $v_{1},\dots,v_{n}$ of backbone vertices. Now assume all
vertices are of degree $4$ or lower. We place them on a horizontal line. For
each $1\leq i\leq n$ at disk $d(v_{i})$, we place its leaf neighbor disks
$d(v_{i}^{t}),d(v_{i}^{b})$ first at the top and then at the bottom of
$d(v_{i})$, see Fig. 7(a), s.t., the clockwise angle $\measuredangle
v_{i}^{t}v_{i}v_{i}^{b}=\frac{4\pi}{3}-2i\varepsilon$. The rotational
$\varepsilon$ offset avoids adjacencies between the leaf disks. While these
offsets can add up, we can choose $\varepsilon$ small enough for every finite
caterpillar, s.t., this is negligible.

Now we assume that not all vertices are of degree 4 or lower. To keep the
entire construction of the backbone $x$-monotone, whenever we encounter a
degree $5$ vertex $u$ after a degree four vertex $v_{k}$, we place
$d(u^{t^{\prime}})$ of its additional leaf $u^{t^{\prime}}$ alternatingly on
the top or the bottom side with a $\frac{\pi}{3}+\varepsilon$ rotational
offset to $d(u^{t})$ (or $d(u^{b})$). We will assume that we placed the disk
at the top. Therefore $\measuredangle
u^{t^{\prime}}uu^{b}\leq\pi-(2k+1)\varepsilon$, i.e., an almost horizontal
connection, see Fig. 7(b).

If the next vertex $x$ has also degree five, then due to Lemma 3 we know that
the sequence is not realizable. Otherwise, we place $d(x)$, s.t., it is
touching $d(u)$ with a $\frac{\pi}{3}+\varepsilon$ rotational offset to
$d(x)$, see Fig. 7(b). We place $d(x^{b})$ at the planned position relative to
$d(x)$ at the bottom, i.e., with a $\frac{\pi}{3}+(k+2)\varepsilon$
counterclockwise offset relative to the $x$-axis, however, we place $d(x^{t})$
almost exactly on top of $d(x)$ with a very small shift of
$\frac{\varepsilon}{Cn}$ orthogonal to $\overline{ux}$, for some large
constant $C$. This prevents touching of $d(u)$ and $d(x^{t})$, without
creating an adjacency between $d(u^{t^{\prime}})$ and $d(x^{t})$.

(a) $\varepsilon$-offsets. $\rho_{k}=\frac{4\pi}{3}-2k\varepsilon$

(b) Placement of $x$ after encountering $u$

(c) $\eta=\eta^{\prime}$ and
$\eta+\eta^{\prime}=\frac{4\pi}{3}-(2k+6)\varepsilon$

(d) $\tau=\tau^{\prime}$ and $\tau+\tau^{\prime}=\pi-(2k+7)\varepsilon$

Figure 7:  Chains of degree-4 vertices are placed in a dense packing formation
with small offsets (a). A degree-5 vertex places an additional leaf on one
side (b). The next vertex $v_{k+3}$ can again be placed with the desired angle
of just over $\frac{2\pi}{3}$ between two neighbors (c). Placement of
$v_{k+3}$ is possible if its degree is 5 (d). Note that, the rotational offset
angles are exaggerated, for better readability.

From this point onwards, we consider the direction of $\overline{ux}$ to be
the direction in which we extend the backbone of the caterpillar. Any
following disk $d(v_{k+3})$ can be placed again in the new extension direction
touching $d(x)$. Its leaf disks $d(v_{k+3}^{t})$ and $d(v_{k+3}^{b})$ can be
placed in their planned positions, i.e. with a clockwise or counterclockwise
offset of $\frac{\pi}{3}+(k+3)\varepsilon$ relative to the new extension
direction, respectively, which results in a clockwise angle $\measuredangle
u_{t}uu_{b}\leq\frac{4\pi}{3}-(2k+6)\varepsilon$. Note that $v_{k+3}$ can have
a degree of four (Fig. 7(c)) or five (Fig. 7(d)) and that at this point, if
$v_{k+3}$ has degree five, we can immediately repeat this procedure.

As a postprocessing step, we remove all degree-$1$ vertices that were added in
the preprocessing step. Then from the above description of the algorithm and
the correctness analysis in Appendix 0.B.2 we obtain the following theorem.

###### Theorem 4.1

Let $G=(V,E)$ be a caterpillar graph. $G$ admits a UDR if and only if $G$ does
not contain any two adjacent degree-$5$ vertices in the backbone path $B_{G}$
of $G$. This property can be tested in linear time and if a UDR exists then it
can be constructed in linear time.

##  5 Weak UDCs of Lobsters on the Triangular Grid

We have shown that recognition of UDRs is -hard for outerplanar graphs and
linear-time solvable for caterpillars, which mirrors the results for UDCs and
weak UDCs; it leaves the recognition complexity for (non-embedded) trees as an
open question for both UDRs and UDCs. For weak UDCs, however, recognition has
been proven -hard for trees [7]. In order to investigate the complexity of
weak UDCs further, we zoom in on the gap between trees and caterpillars and
investigate the graph class of lobsters.

The _spine_ of a weak UDC of a lobster $G$ is the polyline defined by
connecting the centers of all disks belonging to the vertices of $B_{G}$ in
order. A weak UDC is _straight_ , if its spine is a straight line segment.
Similarly, a weak UDC is $x$\- or $y$-monotone, if its spine is $x$\- or
$y$-monotone. Since we consider weak UDCs with contacts between non-adjacent
disks permitted, we focus our attention on weak UDCs placed on a triangular
grid (similarly to previous work on weak UDCs [7]).

###  5.1 Straight Backbone Lobsters

Since any caterpillar $G$, admits a weak UDC if and only if it admits a
straight weak UDC [7] we investigate lobster graphs, which admit a straight
weak UDC. These are not all lobsters, since any simple lobster graph
containing a non-backbone vertex of degree 6 only admits a non-straight weak
UDC. We observe that already for this restricted subclass, a greedy placement
scheme similar to Cleve’s approach [7] for caterpillars is not possible; again
shown by an example.

(a) $G$ has 18 possible weak UDCs

(b) $G^{\prime}$ has 12 possible weak UDCs

Figure 8: The subgraphs of $G$ and $G^{\prime}$ induced by their first three
backbone vertices are equal, however, depending on the following vertices a
different realization of the neighbors of $v_{3}$ is necessary.

We specify two lobster graphs $G$ and $G^{\prime}$, see Fig. 8. It can be
checked via exhaustive enumeration that $G$ admits 18 different weak UDCs,
while $G^{\prime}$ admits only 12. The subgraphs induced by their first three
backbone vertices are identical, however the realization of the descendants of
$v_{3}$ (highlighted in red) is unique for both graphs (up to symmetry) and
dependent on the structure of the graphs beyond this point. We can therefore
not simply scan over the backbone in a greedy manner and fix all positions for
the disks of descendants of a backbone vertex and then continue on to the
next. It is, however, still possible to do this in linear time with dynamic
programming. The requirements for this are actually less strict, as it is
already sufficient to have a strictly $x$-monotone rather than a straight
backbone, which we show in the next section.

###  5.2 Monotone Weak UDCs

If we can guarantee that a lobster can be realized as a strictly $x$-monotone
weak UDC, we can compute such a weak UDC with a linear-time dynamic
programming algorithm. The dynamic program uses the following three
observations.

[$\star$] The number of possible placements of a backbone vertex $v_{i}$ and
its descendants is constant for a fixed position of $v_{i}$.

[$\star$] For a fixed grid position, the number of backbone vertices of a
strictly $x$–monotone weak UDC, who can occupy this position by themselves or
with a descendant is constant. Moreover, the distance in graph between the
first and the last such vertex is constant.

[$\star$] Let $C$ be a sufficiently large constant, and let $A,B$ be two weak
UDC, whose last $C$ backbone vertices have placed themselves and their
descendants in such a manner, that the pattern of occupied grid positions and
the placement of the last backbone vertex is equivalent up to translation and
rotation. Then any extension graph $C$, which can be appended to $A$, s.t.,
the combined graph admits a weak UDC can also be appended to $B$, s.t., their
combined graph admits a weak UDC and vice versa.

With these three claims we obtain the following Lemma.

######  Lemma 4 ($\star$)

Using dynamic programming it can be checked in linear time if a lobster graph
admits an $x$-monotone weak UDC on the triangular grid.

###  5.3 General Lobsters

The algorithm sketched in the previous section recognizes lobster graphs,
which admit a strictly $x$-monotone weak UDC in linear time. Now we set out to
prove that every lobster which admits a weak UDC also admits a strictly
$x$-monotone weak UDC. We prove this by induction. The induction step is done
as a computer-assisted proof. See Appendix 0.D for details.

###### Lemma 5

Every lobster graph, which admits a weak UDC on the triangular grid, also
admits an $x$-monotone weak UDC on the triangular grid.

###### Proof

We use induction on the length of the backbone. The base cases are backbones
of length one, two or three. The spine of any realization is at most a
polyline consisting of two segments and can therefore always be rotated to be
$x$-monotone. The induction hypothesis is, that any lobster graph, with a
backbone of length $k$ admits an $x$-monotone weak UDC. In the induction step
we need to show that any extension to a graph $G^{\prime}$ with a backbone of
length $k+1$, can be realized as a weak UDC if and only if it can be realized
in an $x$-monotone way. The extensions are done by appending a single new
backbone vertex $v_{k+1}$, whose descendants are specified as a sorted list of
the degrees of its direct neighbors. Since the total degree of every vertex is
at most 6, the set $\Gamma$ of options for $v_{k+1}$ is constant (Section
5.2). Let $\Theta$ be the set of possible combinations of already occupied
grid positions where $v_{k+1}$ is placed such that the spine remains
$x$-monotone. Let $\Delta_{6}$ and $\Delta_{3}$ be the sets of possible
placements of disks of descendants of $v_{k+1}$, when $v_{k+1}$ is placed at
one of six (in the unrestricted case) or one of three (in the strictly
$x$-monotone case) positions. Therefore we can enumerate all triples
$(\gamma\in\Gamma,\delta_{3}\in\Delta_{3},\theta\in\Theta)$ and
$(\gamma\in\Gamma,\delta_{6}\in\Delta_{6},\theta\in\Theta)$ and check if they
are realizable. By exhaustive enumeration,333The cases were reduced, by
considering symmetry and infeasibility beforehand. Enumeration was done in the
form of a computer-assisted proof. Details are explained in Appendix 0.D we
have found that for every possible $(\gamma,\delta_{6},\theta)$, which is
realizable, we can find a suitable $(\gamma,\delta_{3},\theta)$, which is
realizable, too. This concludes the induction step.

From Lemmas 4 and 5, we conclude the following theorem.

###### Theorem 5.1

It can be decided linear time if a lobster graph admits a weak UDC on the
triangular grid.

##  6 Conclusions

We have investigated the existing complexity gap for the recognition problem
of UDRs and weak UDCs. In addition to the open problems for various graph
classes in different settings (recall Table 1 in Section 1) there are two main
open questions. First, we have investigated weak UDCs of lobsters on the
triangular grid, however, it is not entirely clear if every lobster, which
admits a weak UDC, also does so on the grid. Second, it seems reasonable to
assume that our enumeration approach can be extended to graph classes beyond
lobsters, which admit a weak UDC at least on the triangular grid. In fact, we
conjecture that every class of trees, in which each vertex has bounded
distance to a central backbone in extension of caterpillars and lobsters, can
be recognized in polynomial time by such an approach.

#### Acknowledgements.

We thank Jonas Cleve and Man-Kwun Chiu for fruitful discussions about the
project during their research visits in Vienna.

## References

  * [1] Bowen, C., Durocher, S., Löffler, M., Rounds, A., Schulz, A., Tóth, C.D.: Realization of simply connected polygonal linkages and recognition of unit disk contact trees. In: Graph Drawing and Network Visualization (GD’15). LNCS, vol. 9411, pp. 447–459. Springer International Publishing (2015). doi:10.1007/978-3-319-27261-0_37
  * [2] Breu, H., Kirkpatrick, D.G.: On the complexity of recognizing intersection and touching graphs of disks. In: Brandenburg, F.J. (ed.) Graph Drawing (GD’95). LNCS, vol. 1027, pp. 88–98. Springer (1996). doi:10.1007/BFb0021793
  * [3] Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. Theory Appl. 9(1–2), 3–24 (1998). doi:10.1016/S0925-7721(97)00014-X
  * [4] Chalopin, J., Gonçalves, D., Ochem, P.: Planar graphs have 1-string representations. Discrete & Computational Geometry 43(3), 626–647 (2010). doi:10.1007/s00454-009-9196-9
  * [5] Chaplick, S., Ueckerdt, T.: Planar graphs as VPG-graphs. In: Didimo, W., Patrignani, M. (eds.) Graph Drawing (GD’12). LNCS, vol. 7704, pp. 174–186. Springer (2013). doi:10.1007/978-3-642-36763-2_16
  * [6] Chiu, M., Cleve, J., Nöllenburg, M.: Recognizing embedded caterpillars with weak unit disk contact representations is NP-hard. CoRR abs/2010.01881 (2020)
  * [7] Cleve, J.: Weak unit disk contact representations for graphs without embedding. CoRR abs/2010.01886 (2020)
  * [8] Felsner, S.: Rectangle and square representations of planar graphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 213–248. Springer (2013). doi:10.1007/978-1-4614-0110-0_12
  * [9] Gonçalves, D., Isenmann, L., Pennarun, C.: Planar graphs as L-intersection or L-contact graphs. In: Discrete Algorithms (SODA’18). pp. 172–184. SIAM (2018). doi:10.1137/1.9781611975031.12
  * [10] Hliněný, P.: Classes and recognition of curve contact graphs. Journal of Combinatorial Theory, Series B 74(1), 87–103 (1998). doi:10.1006/jctb.1998.1846
  * [11] Hliněný, P., Kratochvíl, J.: Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Mathematics 229(1), 101–124 (2001). doi:10.1016/S0012-365X(00)00204-1
  * [12] Klemz, B., Nöllenburg, M., Prutkin, R.: Recognizing weighted disk contact graphs. In: Graph Drawing and Network Visualization (GD’15). LNCS, vol. 9411, pp. 433–446. Springer International Publishing (2015). doi:10.1007/978-3-319-27261-0_36
  * [13] Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Klasse 88, 141–164 (1936)

##  Appendix 0.A Omitted Details of Section 3

Bowen et al. [1] proved that recognizing unit disk contact graphs is NP-hard
for embedded trees, via a reduction from planar 3-SAT, which uses an auxiliary
construction formulated as a realization of a polygonal linkage. Polygonal
linkages are explained in Section 0.A.1. The details of this auxiliary
structure are explained in Section 0.A.2. Then a tree, whose UDC is an
approximation of the auxilliary structure and which mimics the shape and
behaviour of it, is constructed. This construction is summarized in Section
0.A.3.

###  0.A.1 Polygonal Linkages

Bowen et al. [1] considered multiple problems in their work, one of which is
the _polygonal linkage realizability_ (PLR) problem. A polygonal linkage is a
set $\mathcal{P}$ of convex polygons and a set $H$ of hinges. One hinge is a
set of two or more points on the boundaries of distinct polygons. A polygonal
linkage is realizable, if every $p\in\mathcal{P}$ can be placed in the plane,
s.t.

  * •

all polygons are interior disjoint

  * •

for every hinge $h\in H$, all points of the hinge coincide and

  * •

a predefined cyclic order of adjacent polygons around every hinge is kept.

In our case and in the case of this reduction, hinges are only of size two,
i.e., a realization will identify exactly two points on distinct polygons per
hinge. This means that cyclic order around hinges is always kept by default. A
polygonal linkage and its realization are shown in Fig. 9.

(c) A set $\mathcal{P}$ of polygons with hinges

(d) A realization of (a)

Figure 9:  An instance of PLR (a), where points belonging to the same hinge
are indicated with a dotted line connection. A placement of (rotated and/or
translated) copies of the polygons in $\mathcal{P}$ in the plane is a
realization (b) if the points of the same hinge are identified.

###  0.A.2 Auxiliary Structure

The auxilliary structure mimics a hexagonal grid. This grid-like structure is
obtained by using a hexagonal tiling of the plane and then shrinking every
hexagon by a small amount to obtain narrow channels of a fixed height between
two hexagons, where $\varepsilon$ is a sufficiently small constant. At the
corners of the hexagons, three such channels meet to form a junction. The
union of all channels and junctions forms the grid-like structure. In this
grid, a representation of the incidence graph $G_{\phi}$ of the planar 3-SAT
instance $\phi$ is fitted, see Fig. 2.

A variable $v$ of $\phi$ is represented in this grid as an alternating cycle
of channels and junctions, indicated with a grey fill in Fig. 2. In such a
cycle the channels can be filled with smaller hexagons of height $h$, which
are connected to the large hexagon on the side of the channel – which is on
the “inside” of the variable cycle – via a junction. In a channel, one corner
of each of the small hexagons is connected to the large hexagon via a hinge,
s.t., the small hexagon can be “flipped” around this junction. Due to the
chosen size, the hexagon can be realized in one of two states, see Figs. 2 and
2. The distance of the hinges of neighboring small hexagons is chosen in such
a way that the state of one hexagon determines the state of all hexagons in
the channel, see Fig. 2. At each junction, we add an even smaller hexagon with
a hinge to the corner of that large hexagon, which is adjacent to the channels
on either side of the junction in the variable cycle. This propagates the
state of the hexagons in one channel through the junction into the other
channel and so throughout the entire cycle. See Figs. 2 and 2 for a detailed
explanation.

Wire gadgets are alternating paths of channels and junctions, which use the
same mechanism to propagate the state of the hexagons in the channels and
therefore admit two states overall.

Wire gadgets can be connected to a variable cycle at every junction using the
third unoccupied channel and adding a second very small hexagon in the
junction. A wire gadget is considered to transmit the value true, if and only
if, part of the first small hexagon of the first channel of the wire gadget
enters into the junction. By placing the small hexagon on one or the other
corner (cf. Figs. 2 and 2) the truth value which is transmitted can be
“inverted” if necessary.

For every clause in $\phi$, three such wire gadgets are connected to the
variable cycles of the occurring variables and the wires are routed to meet in
a junction. This junction contains a small hexagon connected to the corner of
a large hexagon via a long and very thin rhombus (in place of a line segment),
s.t., an overlap-free realization is only possible, if at least one connected
wire gadget has no hexagon entering the junction and is therefore in a true
state, see Fig. 2.

In order to guarantee a somewhat rigid placement of these hexagons, the entire
construction is surrounded by a set of six huge hexagons, and the hexagons
acting as the faces of the hexagonal grid are column-wise connected (cf. Fig.
10). This restricts the position of the large hexagons to an $N$-neighborhood,
where $N$ is a polynomial of the number of variables and clauses in $\phi$
[1].

Note that the connections between the polygons in the polygonal linkage induce
a tree. In particular note that we can replace the hexagons with outerplanar
graphs and replace the hinges between them with paths of length one to three
and the entire construction remains an outerplanar graph. The same way we can
replace all hexagons with trees and replace the hinges with vertex paths of
length one to three and the entire construction remains a tree.

Figure 10: The composition of the rigid structure as a realization of a
polygonal linkage. Hinges are indicated by points. The figure is a recreation
of a similar figure in [1], augmented with lines, which emphasize the tree-
like structure of connections in the polygonal linkage.

For a more detailed description, a full construction and the proof of the
semi-rigid placement we refer to the original paper of Bowen et al. [1].

###  0.A.3 Approximating the Auxilliary Structure

In order to prove the -hardness for recognition of unit disk contact graphs,
Bowen et al. [1] created $\lambda$-stable approximations of the basic building
blocks of the auxiliary structure (hexagons of varying sizes and long thin
rhombi). A graph is a $\lambda$-stable approximation of a polygon $P$, if the
boundary union of all disks in its UDC is necessarily within a constant
asymmetric Hausdorff distance $\lambda$ of a congruent copy of $P$.

Bowen et al. described the construction procedures for two graphs
$T_{k},T^{\prime}_{k}$, which are $2$-stable approximations of a long thin
rhombus and a regular hexagon. These two graphs are shown in Fig. 11. For the
details of these constructions, we again refer to Bowen et al. [1]. The
construction of our building blocks using outerplanar graphs in Section 3.1
and embedded trees Section 3.2 is based on these graphs.

(a) Graph $T_{k}$ and its UDC

(b) Graph $T^{\prime}_{k}$ and its UDC

Figure 11:  The $2$-stable approximations of a long thin rhombus (a) and a
regular hexagon (b). All Figures are recreations from Bowen et al. [1].

It remains to discuss how the hinges are modeled. Two $\lambda$-stable
approximations $G,G^{\prime}$ of two polygons $P,P^{\prime}$ are connected
with a path of vertices of constant length, if there exists a hinge $h\in H$,
with one point on the boundary of $P$ and the other on the boundary of
$P^{\prime}$. The exact length of the path is dependent on the location of the
hinge. If the hinge is not placed on a corner of either polygon, they are
simply connected via a single cut vertex, and with a path of length three
otherwise, in order to facilitate more movement, which mimics the possibility
of polygons to rotate around hinges. The union of the UDC of two thus
connected graphs $G,G^{\prime}$, remains a constant factor approximation of a
congruent copy of the realization of $P\cup P^{\prime}$.

###  0.A.4 Proofs of Lemmas 1 and 2

To prove Lemmas 1 and 2 we need to establish some initial Lemmas. First a
ladder $L_{k}$ consists of two paths $v_{1},v_{2},\dots,v_{k}$ and
$v_{1}^{\prime},v_{2}^{\prime},\dots,v_{k}^{\prime}$ of vertices – also called
the outer and inner vertices respectively – s.t., each pair
$(v_{i},v_{i}^{\prime})$ is connected with an edge. The blue vertices in Fig.
3 form a ladder, specifically $L_{17}$. A UDR of $L_{17}$ is shown in the blue
disks of Fig. 3.

###### Lemma 6

Let $k\in\mathbb{N}$ and let $\mathcal{D}$ be a UDR of $L_{k}$. Then
$\mathcal{E}_{\mathcal{D}}(L_{k})$ induces the same embedding as shown in Fig.
3, which is outerplanar.

###### Proof

Clearly no disk can be placed inside a UDR of a $C_{4}$, without intersecting
at least two disks of the $C_{4}$. Since every disk $d(v_{i})$ of a vertex
$v_{i}$, which is not part of the $C_{4}$ intersects at most one disk of the
$C_{4}$, this is impossible and the outer face is fixed. Therefore the induced
embedding is unique.

Lemma 6 implies that we can assign a clear “outer side”, i.e.,
$d(v_{1}),\dots,d(v_{k})$ and “inner side”, i.e., $d(v^{\prime}_{1}),\dots
d(v^{\prime}_{k})$ to a UDR of $L_{k}$.

Next we want to ensure that any overall bend towards the outer side is
impossible. For this we will augment $L_{k}$ with additional neighbors. We
restrict the ladders to an odd length and alternatingly add one and two leaf
neighbors, which we will call extension neighbors. The resulting graph can be
seen in Fig. 3.

###### Lemma 7

Let $(v_{1},v_{2},v_{3},v_{4},v_{5})$ be a chain of vertices on the outer side
of a ladder $L_{k}$ with one, two, one, two and one extension neighbor
respectively. Then the sum of angles $\gamma=\measuredangle
v_{3}v_{2}v_{1}+\measuredangle v_{4}v_{3}v_{2}+\measuredangle v_{5}v_{4}v_{3}$
in a UDR of $L_{k}$ is smaller than $3\pi$, i.e., overall we bend more towards
the inner side than towards the outer side.

###### Proof

We will refer to the two extension neighbors of $v_{2}$ as $a$ and
$a^{\prime}$, both of which are placed on the outer side of the ladder.
Similar we will call the extension neighbors of $v_{4}$, $b$ and $b^{\prime}$.
The singular extension neighbor of $v_{3}$, will be referred to as $c$. The
naming is also shown in Fig. 12(a). Without loss of generality, we assume that
the clockwise order on $v_{2}$ is $(v_{1},a,a^{\prime},v_{3},v^{\prime}_{2})$
and analogue the clockwise order on $v_{4}$ is
$(v_{3},b,b^{\prime},v_{5},v_{4}^{\prime})$. Figs. 12(a) and 12(c) depict this
placement and its UDR.

(a) Arrangement

(b) Increasing $\measuredangle v_{4}v_{3}v_{2}$ decreases $\measuredangle
v_{3}v_{2}v_{1}$ and $\measuredangle v_{5}v_{4}v_{3}$

(c) UDR of (a)

(d) First position

(e) Second position

(f) Third position

Figure 12: Figures for Lemma 7. (a) Is the graph as stated in Lemma 7. (b) If
$d(c)$ is moved outwards to facilitate an angle $\measuredangle
v_{4}v_{3}v_{2}=\pi+\varphi$, i.e., a local outwards bend, it enforces at the
same time an inwards bend of $\varphi$ at $\measuredangle v_{3}v_{2}v_{1}$ and
$\measuredangle v_{5}v_{4}v_{3}$. (c) A valid UDR of (a) including the
$\varepsilon$ gaps between disks, when necessary. (d-f) Extreme positions of
(c), s.t., $\measuredangle v_{2}v_{3}v_{4}=\pi$ (d) or $\measuredangle
v_{2}v_{3}v_{4}=\frac{2\pi}{3}$ (e-f).

First observe that $\measuredangle v_{1}v_{2}a>\frac{\pi}{3}$, since
$|{v_{1}v_{2}}|\leq 2,|{v_{2}a}|\leq 2$ and $|{v_{1}a}|>2$. For the same
reason we have $\measuredangle av_{2}a^{\prime}>\frac{\pi}{3}$ and
$\measuredangle a^{\prime}v_{2}v_{3}>\frac{\pi}{3}$. This means that

$\measuredangle v_{1}v_{2}v_{3}=\measuredangle v_{1}v_{2}a+\measuredangle
av_{2}a^{\prime}+\measuredangle a^{\prime}v_{2}v_{3}>\pi$

and similarly $\measuredangle v_{3}v_{4}v_{5}>\pi$.

Now we will distinguish two extremes at $v_{3}$. In the first extreme position
$d(c)$ is placed almost on top of $d(v_{3})$, s.t., $\measuredangle
v_{2}v_{3}c=\measuredangle cv_{3}v_{4}=\alpha$ and $\alpha$ tends toward
$\frac{\pi}{2}$ as $|v_{3}c|$ approaches 0. The extreme placement with
$|v_{3}c|$ equal to 0 is shown in Fig. 12(d). This results in $\measuredangle
v_{2}v_{3}v_{4}>\pi$. To reach the second extreme (cf. Fig. 12(e)) $d(c)$ is
moved outwards. As $|v_{3}c|$ increases, it facilitates a local outward bend
and an angle $\measuredangle v_{2}v_{3}v_{4}>\pi-\varphi$, where
$\varphi=\cos^{-1}\left(\frac{|v_{2}c|^{2}+|v_{2}v_{3}|^{2}-|v_{3}c|^{2}}{2|v_{2}c||v_{2}v_{3}|}\right)$,
see Fig. 12(b). However, in order to maximize this bend, $v_{2}$ and $v_{4}$
are moved into the resulting gap between $v_{3}$ and $c$, s.t., the distances
$|v_{2}c|$ and $|v_{4}c|$ are equal to $2+\varepsilon^{\prime}$, where
$\varepsilon^{\prime}$ is a very small constant. In particular we have
$\measuredangle a^{\prime}v_{2}c>\frac{\pi}{3}$, and similarly $\measuredangle
cv_{4}b>\frac{\pi}{3}$. Finally this leads to the following values:

$\displaystyle\measuredangle v_{1}v_{2}v_{3}$ $\displaystyle=\measuredangle
v_{1}v_{2}a+\measuredangle av_{2}a^{\prime}+\measuredangle
a^{\prime}v_{2}c+\measuredangle
cv_{2}v_{3}\geq\frac{\pi}{3}+\frac{\pi}{3}+\frac{\pi}{3}+\varphi=\pi+\varphi$
$\displaystyle\measuredangle v_{3}v_{4}v_{5}$ $\displaystyle=\measuredangle
v_{3}v_{4}c+\measuredangle cv_{4}b+\measuredangle
bv_{4}b^{\prime}+\measuredangle
b^{\prime}v_{4}v_{5}\geq\varphi+\frac{\pi}{3}+\frac{\pi}{3}+\frac{\pi}{3}=\pi+\varphi$

Clearly the overall bend towards the inside is minimized, if $\varphi$ and
therefore $|v_{3}c|$ is minimal, i.e., we are as close as possible to the
first extreme state. Since $|v_{3}c|>0$, we have $\measuredangle
v_{2}v_{3}v_{4}>\pi$ and finally

$\gamma=\measuredangle v_{1}v_{2}v_{3}+\measuredangle
v_{2}v_{3}v_{4}+\measuredangle v_{3}v_{4}v_{5}>3\pi$

Note that the second extreme position can also be achieved by using more
overlap between $d(v_{2})$ or $d(v_{4})$ and one of their extension neighbors,
however, this configuration forces $\measuredangle av_{2}v_{3}$ and
$\measuredangle v_{3}v_{4}b^{\prime}$ to approach $\pi$ and therefore results
in a similar overall inwards bend by $\varphi$, as shown in Fig. 12(f).

We can also add a third extension neighbor to an outer vertex of a ladder to
force an even more pronounced bend towards the inside. The corresponding graph
construction is shown in Fig. 3 and a valid UDR in Fig. 3.

###### Lemma 8

Let $(v_{1},v_{2},v_{3})$ be a chain of outside vertices of a ladder, s.t.,
$v_{2}$ has degree 5, i.e., 3 extension neighbors. Then the angle
$\measuredangle v_{3}v_{2}v_{1}$ is smaller than $\frac{2\pi}{3}$, i.e.,
overall we bend at least $60^{\circ}$ towards the inner side.

###### Proof

Note that the argument for the inward directed bend at $v_{2}$ and $v_{4}$ in
the proof of Lemma 7 was simply based on the number of extension neighbors. By
increasing that number to 3, the lemma immediately follows.

We call this construction a corner connector. The corner connector contains a
5-cycle, however similar to a 4-cycle, it is impossible to place a disk inside
such a cycle without creating wrong adjacencies through overlap.

Finally we want to state some measure for the height of a UDR of an augmented
$L_{k}$

###### Lemma 9

The height the smallest bounding rectangle of a UDR of an augmented ladder
$L_{k}$ is at least $2\sqrt{3}+2-\varepsilon^{\prime\prime}$, where
$\varepsilon^{\prime\prime}$ is a very small constant, which is the height of
the smallest bounding box of an optimal packing of three rows of unit disks
minus $\varepsilon^{\prime\prime}$.

###### Proof

The distance between the extension neighbors and the outer disks of the ladder
has been argued in the proof of Lemma 7. Recall that the disks of the outside
vertices of the ladder with a single extension neighbor are almost completely
covered by it. Let $d(v_{k})$ be such a covered disk. Its adjacent disk
$d(v_{k}^{\prime})$ on the inside of the ladder can therefore only overlap a
very small amount with $d(v_{k})$. Since $d(v^{\prime}_{k})$ is disjoint from
$d(v_{k-1})$ and $d(v_{k+1})$, the extreme position (see Fig. 12(d)) results
in the smallest overall height of the ladder, which is the height of the dense
packing of three rows of unit disks, i.e., $2\sqrt{3}+2$ minus the small
amount $\varepsilon^{\prime\prime}$ which is attributed to the small possible
overlap of $d(v_{k}^{\prime})$ and $d(v_{k})$.

Now we have all necessities to describe the construction of the $7$-stable
approximations of a long thin rhombus (Lemma 1) and a regular hexagon (Lemma
2). Two ladders $L_{k}$ and $L_{k}^{\prime}$ are placed opposite each other
and connected on one end with three corner connectors as shown in Fig. 4. Note
that the horizontal distance between $c_{0}$ and $v_{1}$ is four. See 1

###### Proof

We can assume that $v_{0}=(0,0)$ and that $c_{0}=(-2,0)$. We define a point
$l_{0}=(2k+4,0)$ on the positive $x$-axis with.

We place a congruent copy of the rhombus, s.t., the long diagonal aligns with
$\overline{c_{0}l_{0}}$, and one corner point coincides with the leftmost
point of $c_{0}$, which is at $(-3,0)$. At every point the upper and lower
boundary of the rhombus has a vertical distance of $\delta\in[0,3\sqrt{3}+1]$
to $\overline{c_{0}l_{0}}$. Due to Lemmas 7 and 8, the overall bend of $L_{k}$
and $L^{\prime}_{k}$ has to be towards the inner side. In fact the position
depicted in the Fig. 4 is the limit and would require an additional
infinitesimal bend inwards to be valid. A consequence is that $c_{0}$ and any
$a_{i}$, have a maximal vertical distance of $3\sqrt{3}$ and therefore any
point on the boundary of any disk has at most a vertical distance of
$3\sqrt{3}+1\approx 6.196<7$ to $\overline{c_{0}l_{0}}$.

Clearly the UDRs of $L_{k}$ and $L^{\prime}_{k}$ are completely overlap-free
and therefore a tight packing as indicated in Fig. 4 is the narrowest possible
configuration (including a small gap between the ladders).

Now consider, that the smallest rectangular bounding box of the disks of the
of outer vertices $v_{1},\dots,v_{k}$ and $v_{-1},\dots,v_{-k}$ (as labeled in
Fig. 4) and their extension neighbors have a combined height of at least
$3\sqrt{3}+2$, which is the height of an optimal packing of four rows of unit
disks. Therefore, at every point, there is part of the outline of $G^{R}_{k}$
on or above, and on or below ${c_{0}l_{0}}$ and the distance of the boundary
of the union of all disks and the boundary of the rhombus is at most the
distance of the rhombus itself to $\overline{c_{0}l_{0}}$, which as stated
before, is $3\sqrt{3}+1<7$.

Next we will create a $7$-stable approximation $G^{H}_{k}$ of a regular
hexagon by tracing the outline of a hexagon with ladders and corner connectors
as shown with the blue and the red disks in Fig. 5(a). Every side of the
hexagon is represented by a $L_{k-3}$. Let $L^{1}_{j},L^{2}_{j}$ be two
ladders, and let $v^{k}_{i}$ and $u^{k}_{i}$ be the $i$-th outer and inner
vertices of $L^{k}_{j}$ respectively. At a corner, where $L^{1}_{j}$ and
$L^{2}_{j}$ meet, we connect $u^{1}_{j}$ and $u^{2}_{1}$ with an edge.
Further, we connect the vertex $v_{c}$ of the corner connector with
$v^{1}_{j}$ and $v^{2}_{1}$, thereby connecting the two ladders with a corner
connector. The construction is depicted in Fig. 3. Six ladders are connected
in this fashion through the use of five corner connectors, leaving the first
and the last ladder disconnected. This forms the outer hull of the hexagon,
shown in Fig. 5(a).

Since bends towards the outer side are impossible, we next need to control the
possible deformation of a UDR of our construction towards the inner side. To
achieve this, we add ladders to our construction on the inside of the hull,
reminiscent of our construction of $G^{R}_{k}$. We chose the size of the
hexagon, s.t., the inner area of a UDR of the hull admits the placement of
$2m$ ladders ($m\in\mathbb{N}$ on the top and on the bottom, each) and that in
a UDR, which is an optimal packing of disks, there is no space to add further
disks in the gaps, without creating false adjacencies.

See 2

###### Proof

By combining Lemmas 7 and 8, we conclude that a UDR of a such constructed
outer hull does not exceed the boundary of a translated and/or rotated copy of
the hexagon outlined as a dashed line in Fig. 5(a), which has a side length of
$2k-1$.

Some movement towards the inside is possible. By moving all ladders on the
inside in the top half down by a complete row, including the ladder tracing
the upper horizontal edge of the hexagon, we again arrive at an optimal
packing of pairwise disjoint ladders, which contribute (due to Lemma 9) at
least their full height of $2\sqrt{3}+2-\varepsilon^{\prime\prime}$ (again
$\varepsilon^{\prime\prime}$ is a very small constant value) to the height of
any UDR of the construction and theoretically, there is space to fold the
right outer arm inward as depicted in 13(a). Even though the depicted folding
of this outer arm into the optimal packing position is not possible, due to
the construction, for increasingly long outer arms, we can get arbitrarily
close to this packing. Therefore we analyze the (unreachable) worst case of
the optimal packing, in which the farthest point from the boundary of the
hexagon has a distance of
$3\sqrt{3}+1+O(k)\cdot\varepsilon^{\prime\prime}<3\sqrt{3}+1<7$, we conclude
that no point on the boundary of the union of all disks in the UDR of a
$G^{H}_{k}$ has a larger distance than 7 to a point on the boundary of the
green dashed hexagon.

(a) Compact state of $G^{H}_{k}$

(b) Compact state of $T^{H}_{k}$

Figure 13: In the most compact position, the UDR of $G^{H}_{k}$ and
$T^{H}_{k}$ can – similar to the rhombus – fold all inner arms to one side
(here to the lower side), and theoretically, there is space to fold the outer
arms inward as depicted. The UDR of the arms are however again pairwise
overlap free and the largest reachable distance any point on the boundary of
the union of disks can have from the approximated regular hexagon is
$3\sqrt{3}+1$.

###  0.A.5 Proof of Theorem 3.2

See 3.2

###### Proof

By modifying the construction of the previous section, we can prove that given
a tree $T$ and an embedding $\mathcal{E}(T)$ it is -hard to decide if $T$
admits a UDR $\mathcal{D}$, s.t.,
$\mathcal{E}_{\mathcal{D}}(T)=\mathcal{E}(T)$. In particular, we construct two
graphs $T^{R}_{k}$, $T^{H}_{k}$, which are both trees and $7$-stable
approximations of a long thin rhombus and a regular hexagon respectively.

In the previous proof, we needed to construct ladders in a very specific way
to force the placement of the disks of extension neighbors to one side. This
was done by adding the inner vertices, which made the graphs outerplanar.
Since in this setting the embedding is fixed, we can remove the inner
vertices, which leaves the outer vertices and the extension neighbors. Observe
that the leftover graph is a tree. The same holds for the corner connector.

Lemma 7 and Lemma 8 can be directly applied to this new construction, since no
assumption was made about the placement of the inner vertices outside of their
function of forcing the disks of the extension neighbors to be placed on the
outside. This is now guaranteed by the embedding that is given as input.

To construct $T^{R}_{k}$, remove the inner vertices of a $G^{R}_{k}$. Now the
space between the two arms is large enough to accommodate one of the arms
folding in on itself. To prevent this, we add a third arm to the construction,
as shown in Fig. 6. Recall that the outer arms of the construction cannot bend
farther outwards than to the horizontal position in Fig. 6. Now again, no
singular disk can be fit into the gap between the arms.

Next note that even without the inner vertices of the ladders, the three arms
of a $T^{R}_{k}$ must together always be at least as high as an optimal
packing of six rows of disks, which results in a height of $5\sqrt{3}+2$.
Therefore, at any given horizontal point, some part of the boundary of the
union of all disks in a UDR of $T^{R}_{k}$ is either on or above
$\overline{c_{0}l_{0}}$. Since any point on the approximated rhombus is at
most $3\sqrt{3}+1<7$ away from this line, $T^{R}_{k}$ is a $7$-stable
approximation of a long thin rhombus.

We perform a similar adaption of $G^{H}_{k}$ to obtain $T^{H}_{k}$, a
$7$-stable approximation of a regular Hexagon. Analogously to $T^{R}_{k}$ the
outer hull, which traces the hexagon is the same as for $G^{H}_{k}$, with all
inner vertices removed from the ladders. The relative placement of disks of
extension neighbors to the outside is fixed, by the given embedding. Therefore
we can always place a congruent translated and/or rotated copy of the hexagon
we want to approximate over the UDR of the construction shown in Fig. 5(b),
s.t., the UDR is completely contained.

The exact placement of the inner ladder is slightly different as before. We
still fill the inside in such a manner, that the space between all upper and
lower inner ladders does not admit the placement of an additional disk in a
UDR, if realized as an optimal packing (cf. Fig. 5(b)), however this requires
an asymmetric construction, which places one additional ladder on one of the
two sides, here to the bottom (similar to the construction of $T^{R}_{k}$).
Movement to the inside can be analyzed with a similar approach as before, by
considering the closest placement to the inside of any of the arms, resulting
in an optimal packing of the entire upper half of the construction, as seen in
Fig. 13(b). Again this unobtainable worst case scenario leads to a maximal
distance of $3\sqrt{3}+1<7$ between the outline of any UDR of $T^{H}_{k}$ and
the hexagon.

We therefore obtain again $5$-stable approximations of a long thin rhombus and
a hexagon and hardness follows in the same fashion as for Theorem 3.1.

##  Appendix 0.B Omitted Details of Section 4

###  0.B.1 Proof of Lemma 3

See 3

###### Proof

Let $u_{1},u_{2},x$ (resp. $v_{1},v_{2},x^{\prime}$) be the first, second and
third neighbor of $u$ (resp. $v$) in counterclockwise/clockwise order,
respectively. We assume a placement of $d(u_{1}),d(u_{2}),d(v_{1})$ and
$d(v_{2})$ as depicted in Fig. 14. Since $x$ is adjacent to $u$ and not
adjacent to $u_{2}$ and $v$, the possible space of placing the center of
$d(x)$ is restricted to a small open fan-shaped area (see Fig. 14(c)). A
symmetric area exists for $d(x^{\prime})$ as well. Moreover, all three pairs
of points with a distance of at least two, namely Figs. 14(d) and 14(f) and a
symmetric version of Fig. 14(f), are on the boundaries of these areas.
Therefore no such pair exists in the open fan-shaped areas. Note that a
similar argument holds for the lower side and any rotation of
$d(u_{1}),d(u_{2}),d(v_{1})$ or $d(v_{2})$ will decrease the area on one side.
This completes the proof.

(a) Two disks to be placed

(b) $|xu_{2}|,|xv|>2$

(c) $|xu|\leq 2$

(d) First extreme

(e) $\leavevmode\hbox to9.31pt{\vbox
to6.25pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@roundjoin\pgfsys@invoke{ }{{}} {}{}{}{}{}{}{}
{}\pgfsys@moveto{8.91003pt}{5.85pt}\pgfsys@lineto{3.51003pt}{5.85pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@lineto{5.40001pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}uvpu_{2}$ is a rhombus

-1

(f) Second extreme

Figure 14: Visualization of the proof steps of Lemma 3. The area highlighted
in orange illustrates possible placements for the center of $d(x)$, which is
progressively restricted by its adjacent and non-adjacent neighbors.

###  0.B.2 Correctness

If a caterpillar contains consecutive degree 5 vertices we reject it as it has
no UDR. In any other case, the algorithm above can represent it in a way,
s.t., at any point the angle between a backbone vertex and its left most-top
and left-most bottom leaf is less than $\pi$. As long as this property holds,
we can always add a new backbone vertex. Moreover, if the sequence is extended
by a backbone vertex of at most degree 4, this property immediately holds
again. If the sequence is extended by a backbone vertex of degree 5, a
backbone vertex of degree at most 4 must follow. Once we place this degree 4
vertex appropriately, cf. Fig. 7(b), then the property immediately holds
again.

##  Appendix 0.C Omitted Details of Section 5

See 5.2

###### Proof

The vertex $v$ can only be placed at one of three possible grid positions. For
each position $p$ at which $v$ can be placed, every placement of $v$ and its
descendants corresponds to a subset of the constant size set $S(p)$, which
yields again a constant number of placements.

See 5.2

###### Proof

Clearly the number of grid positions inside a circle of radius 2 are constant.
Therefore only a constant number of previously placed backbone vertices could
have possibly been placed a this grid position or placed one of their
descendants on it. Since the weak UDC is strictly $x$–monotone, every backbone
vertex must be placed to the right of the previous one. In particular that
means that only a constant number of backbone vertices can have a distance
smaller or equal to 2 in $x$ direction to the grid position and moreover, the
graph distance between the first and last such vertex has to be constant.
Since every graph, which possible can occupy the grid position has to have an
$x$-distance of less or equal to 2, this concludes the proof.

See 5.2

###### Proof

Let $U$ be the weak UDC of $A$ and $C$. Now we take the subpart of $U$ induced
by vertices of $C$. Assume w.l.o.g., that the disk of the first backbone
vertex of $C$ was placed one grid position to the right of the disk of the
last backbone vertex of $B$. We now translate this part, s.t., the disk of the
first backbone vertex of $C$ is placed one grid position to the right of the
last backbone vertex of $B$. Since $B$ and $A$ had the exact same set of
already occupied grid positions, this is a valid weak UDC of $B$.

See 4

###### Proof

The dynamic program starts at the first backbone vertex $V_{1}$, which is
w.l.o.g., placed at a fixed position and enumerates all possible placements of
the descendants of $v_{1}$. Due to Section 5.2, this can be done in $O(1)$
time. Every single placement yields a pattern of occupied positions on the
grid. Note that two placements, which yield the same occupation pattern and
place $v_{1}$ at the same position relative to that pattern (up to translation
and rotation) are indistinguishable, when considering the obstruction they
pose for the rest of the weak UDC, due to Section 5.2. We save all possible
occupation patterns together with the position of the previously placed
backbone vertex as a record. After processing the first backbone vertex, we
therefore clearly have a constant number of records.

When the dynamic program continues on from the $(i-1)$-th to the $i$-th
backbone vertex $v_{i}$ it needs to place the new backbone vertex at a
specific position. Every such position $p$ has a constant set of grid
positions, which are at most at a grid distance of 2 to $p$. Note that these
grid positions can be occupied by descendants of previous backbone vertices,
however, due to Section 5.2 these backbone vertices have at most a constant
distance in the graph to $v_{i}$. Therefore the dynamic program only needs to
remember the exact occupation pattern for a constant number of previously
placed backbone vertices.

In particular this means, that for all possible occupation patterns (a
constant number per backbone vertex) of all relevant previous backbone
vertices (a constant number) we need to save all possible placements (a
constant number per backbone vertex and occupation pattern). We call one such
saved combination, together with the position of the previously placed
backbone vertex, a _record_ and such a record is clearly of constant size.

For every single record, we need to enumerate all possible placements of the
descendants of $v_{i}$. Due to Section 5.2, this is also a constant number.
Finally we can check if the placement is valid for this record in constant
time. For every record, we now save for every possible valid placement of
$v_{i}$ and its descendants only the information of the occupied grid
positions for $v_{i}$ and the required constant number of predecessors of the
backbone. The crucial observation is that we do not need to differentiate
between two records, which are equivalent as defined in Section 5.2. If we do
consider records, whose last $C$ backbone vertices induce the exact same
pattern and whose last backbone vertex was placed at the exact same position
(up to translation), then it is clear that only a constant number of unique
records exist for a single backbone vertex. In particular, $v_{i+1}$ starts
only with a constant number of records to check. This results in only an
overall constant time to process a single backbone vertex.

##  Appendix 0.D Computer Assisted Proof of Lemma 5

Here we aim to provide a detailed overview of our computer assisted approach
of the induction step for the proof of Lemma 5. Recall that the induction
hypothesis is as follows. Any lobster graph $G$, with a backbone of length $k$
admits a strictly $x$-monotone weak UDC. In the induction step we need to
prove that any extension to a lobster graph $G^{\prime}$ with a backbone of
length $k+1$ also admits an $x$-monotone weak UDC. Let $v_{1},\dots,v_{k+1}$
be the vertices of $B_{G^{\prime}}$. Note that $v_{k+1}$ needs to be placed,
s.t., it is in contact with $v_{k}$ and, in a strictly $x$-monotone weak UDC,
$v_{k+1}$ can be placed at one of three possible grid positions
$p_{1},p_{2},p_{3}$, while in a weak UDC it can be placed at one of six
possible grid positions $p_{1},\dots,p_{6}$ (at least one of which will
already be occupied by $v_{k}$). If we can find an instance of a graph
$G^{\prime}$, s.t., $v_{k+1}$ is forced to be placed at one of the positions
$p_{4},p_{5},p_{6}$ in order to realize a weak UDC of $G^{\prime}$, we know
that the Theorem would be false. The crucial observation is that we can
enumerate for a given graph $G$ all possible extensions $G^{\prime}$, since
the maximum degree of every vertex is naturally bounded by six. Moreover the
exact structure of $G$ is not relevant, when investigating if $G^{\prime}$
admits a weak UDC. But rather, we want to know to what extent the already
placed disks of $G$ can interfere with a placement of disks belonging to
$v_{k+1}$ and its neighbors.

###  0.D.1 Enumerating All Combinations of Free Grid Positions

Note that the set of grid positions, which can be used to place $v_{k+1}$ or
one of its neighbors is a constant size set of 29 positions, see Fig. 15(a).

(a)

(b)

(c)

Figure 15:  (a) A constant size set of grid positions, which could be occupied
by $v_{k+1}$ or one of its neighbors for a fixed position of $v_{k}$ (at $-1$)
and a possible placement of $v_{k+1}$ at either 7, 10 or 14. Positions, which
are necessarily free (assuming an already $x$-monotone placement of $v_{1}$ up
to $v_{k}$) are $21,\dots,27$. (b) All cases, how the previous backbone could
be connected to the position of $v_{k}$. The numbers indicate the occupied
positions of the previous backbone vertices in each case. The top right case
is covered, because the center case is a subset of it. The bottom three cases
are covered by symmetry.

We assume w.l.o.g. that $v_{k}$ was placed at grid position $-1$. The
positions we need to consider, when looking at obstructions is a smaller set
than the full 29, as positions $21,\dots,27$ can not possibly be occupied,
since they have a minimal grid distance of three to any possible previous
backbone vertex position (Note that we denote the grid distance between two
neighboring grid positions as one, even though the actual distance has to be
two to accommodate the unit disks). Further we can assume $-1$ to be blocked
as $v_{k}$ is placed at this position

Next we can assume that the grid position $-1$ has to be connected to the left
hand side of the area outlined in red in see Fig. 15(a), as there must be at
the very least an incoming path of backbone vertices. Every such $x$-monotone
path on the grid starting at any point to the left of $-$ on the boundary of
the red region and ending at $-1$ has a maximum length of three. Note that our
base cases cover all backbone lengths up to a length of three. Various
possibilities exist for such a path, however we only need to consider three,
see Fig. 15(b). The top right case is covered, because it is indistinguishable
from the center case, when a single neighbor of either $v_{k}$ or $v_{k-1}$ is
placed at position 6. The bottom three cases are simply symmetric to the top
three cases.

This now leaves us with two cases with a set of 19 possibly occupied grid
positions and one with 20. From here on out we assume that we represent these
grid positions as three lists of boolean variables
$L_{C},C\in\\{\\{6,2\\},\\{6,5\\},\\{9\\}\\}$ of length 21, where $L_{c}[i]$
($\neg L_{c}[i]$) means that the position is (not) occupied. Clearly some of
these positions are fixed to be true, e.g., $c\in C\implies L_{C}[c]$, i.e.,
the grid positions, which are occupied by disks of the previous backbone
vertices are guaranteed to be blocked. Moreover, some of the positions are
also guaranteed to be not occupied. For example the grid positions 19 and 20
do not have any path to either $-1$, 2, 6, or any possible position of a
previous backbone disk - recall that the realization is $x$-monotone up to
$v_{k}$ \- of grid distance 2 or shorter and can therefore not be occupied by
a previously placed disk. All possible combinations of the values in these
lists, still leaves us with two times $2^{19}$ plus $2^{20}$ (since
$L_{\\{6,2\\}}$ and $L_{\\{6,5\\}}$ have two blocked spots and $L_{\\{9\\}}$
has one) cases.

We can reduce the number even further when considering the implication of one
true value on all other values in a list $L_{C}$. For this we first set every
singular entry in a list to true and consider its implications. One example is
shown in Fig. 15(c), where we consider the implications of setting
$L_{\\{6,2\\}}[7]$. Since $7$ is occupied, the next backbone disk can only be
placed at positions 9, 10, 13 or 14. Note that positions 0, 1 and 3 do not
have a free path (that is a sequence of free grid position), s.t., the start
and end point of this path have grid distance two to either one of these
positions. Therefore, They are unusable to any descendent of $v_{k+1}$ in a
weak UDC. We can consider them occupied. This implication can be formulated as

$L_{\\{6,2\\}}[7]\implies L_{\\{6,2\\}}[0]\land L_{\\{6,2\\}}[1]\land
L_{\\{6,2\\}}[3]$

We can manually consider every single position in the grid and their
implications on all other positions in each of the three scenarios. All such
implications are visualized as an implication matrix in Figs. 16(a), 17(a) and
18(a).

(a) Implications of singular grid positions

(b) Implications of sets of grid positions

Figure 16: Implications of singular grid positions being occupied on all other
grid positions in $L_{\\{6,2\\}}$. Red blocks indicate, the column number
implies the row number. Light red blocks indicate a trivial or previously
determined implication. Green blocks indicate guaranteed free positions. Grey
overlay indicates that the implication of these columns was not considered (as
they are free).

(a) Implications of singular grid positions

(b) Implications of sets of grid positions

Figure 17: Implications of singular grid positions being occupied on all other
grid positions in $L_{\\{6,5\\}}$. Red blocks indicate, the column number
implies the row number. Light red blocks indicate a trivial or previously
determined implication. Green blocks indicate guaranteed free positions. Grey
overlay indicates that the implication of these columns was not considered (as
they are free).

(a) Implications of singular grid positions

(b) Implications of sets of grid positions

Figure 18: Implications of singular grid positions being occupied on all other
grid positions in $L_{\\{9\\}}$. Red blocks indicate, the column number
implies the row number. Light red blocks indicate a trivial or previously
determined implication. Green blocks indicate guaranteed free positions. Grey
overlay indicates that the implication of these columns was not considered (as
they are free).

We further considered the implications of some sets of grid positions, e.g.,
$L_{\\{6,2\\}}[7]\land L_{\\{6,2\\}}[10]\implies L_{\\{6,2\\}}[4]$, i.e., in
the $L_{\\{6,2\\}}$ setting, if both 7 and 10 are occupied, 4 is unreachable
and can therefore be considered occupied. All such implications are again
visualized in an implication matrix in Figs. 16(b), 17(b) and 18(b).

We then generate all possible combinations of Boolean variables for the three
lists $L_{\\{6,2\\}}$, $L_{\\{6,5\\}}$ and $L_{\\{9\\}}$, but omit any
combination, which contradicts any of the implications, we have identified,
e.g., if any combination has

$L_{\\{6,2\\}}[7]\land\neg L_{\\{6,2\\}}[0]$

then we can omit it and similar for all other implications.

###  0.D.2 Enumerating all possible Extensions of $G$ to $G^{\prime}$

The next crucial observation is that the number of the neighbors of $v_{k+1}$
and the number of their neighbors is bounded by 5, i.e., $v_{k}{k+1}$ can have
at most 5 neighbors (excluding $v_{k}$), which can have at most 5 neighbors
themselves (excluding $v_{k+1}$). Again we represent $v_{k+1}$ as a sorted
list $L_{v}$ of length equal to the number of neighbors (excluding $v_{k}$),
s.t., for every neighbor $v_{n}$ of $v_{k+1}$, there is an $i$, s.t.,
$L_{v}[i]$ is equal to the number of neighbors of $v_{n}$ (excluding
$v_{k+1}$). For example, the first backbone vertex of Fig. 1, would be
represented as $[3,2,1]$.

Now it is clear that we can employ again an exhaustive enumeration to
construct every sorted list of length 5 or lower, with all possible
combination of values between $0$ and $5$. We can however again identify some
exclusion criteria, based on structures, which make a graph unrealizable
outright. These criteria are:

  * •

If the total number of vertices is larger than the not occupied entries in
$L_{c}$, the graph is not realizable

  * •

Depending on the number of neighbors (excluding $v_{k+1}$) we can identify,
how many grid positions at grid distance 1 to the placement of $v_{k+1}$, a
single neighbor will occupy

    * –

If $L_{v}[i]$ equals 5, it will occupy at least 3 such spaces, (2
additionally)

    * –

If $L_{v}[i]$ equals 4, it will occupy at least 2 such spaces (1 additionally)

    * –

If there exists $i,i^{\prime},i^{\prime\prime},i^{\prime\prime\prime}$, s.t.,
$L_{v}[i],L_{v}[i^{\prime}],L_{v}[i^{\prime\prime}]$ are equal or greater than
3 and $L_{v}[i^{\prime\prime\prime}]$ is equal or greater than 2, these
neighbors will together occupy at least 5 such spaces (1 additionally)

(a) $[5]$

(b) $[4]$

(c) $[4]$

(d) $[3,3,3,2]$

(e) $[3,3,3,2]$

Figure 19: Additionally occupied grid positions at grid distance 1 from the
position of $v_{k+1}$ (grey). A descendant, which is non-adjacent to
$v_{k+1}$, but occupies a grid position at grid distance 1 to $v_{k+1}$ is
colored in light red. The realization in (d) is not valid. The subcaptions are
according to the list notation of the neighbors as used in the text.

If any of the first two criteria applies or the number of neighbors of
$v_{k+1}$ plus the number of additionally occupied grid positions (indicated
in parenthesis above) is greater than the number of free spaces at grid
distance 1 to the chosen position of $v_{k+1}$, we can disregards this sorted
list.

With these tools, we can now generate the set of instances
$I=(\Gamma\times\Theta)\setminus\Xi$, where $\Xi$ is any combination of an
element $\gamma\in\Gamma$ and $\theta\in\Theta$, s.t., either $\gamma$ or
$\theta$ pr the combination of both could be excluded based on the criteria
outlined above. The size of $I$ is $|I|=7017913$.

###  0.D.3 Enumerating All Possible Realizations in a Given Setting

Finally we use an exhaustive enumeration of possible placement of the
descendants of $v_{k+1}$, for each of the three or six possible placements of
$v_{k+1}$ to generate $\Delta_{3}$ and $\Delta_{6}$. For this we consider a
fixed position of $v_{k+1}$. Then we consider every possible placement of its
neighbors on the grid positions at grid distance 1 to $v_{k+1}$. If no such
placement exists, the setting is not realizable. Next for a neighbor $v_{n}$
of $v_{k+1}$ we consider all placements of its neighbors (excluding $v_{k+1}$)
at the still free grid positions. If this does not exist for any $v_{n}$, the
setting is not realizable. Now we have multiple sets of possible realizations
of the neighbors of every $v_{n}$. We finally consider every combination of
choosing one element out of each of these sets, s.t., no two disks occupy the
same grid positions. If no such combination exists, the setting is not
realizable. Otherwise the set of all combinations is a complete enumeration of
all realizations of $v_{k+1}$ and all of its descendants.