neither of them induces a framework conflict, and they cross each other, then
we say that such drawings induce an external conflict. Similarly, if the
drawings of $\triangle_{i}$ and $\triangle_{j}$ in $\Gamma$ are both internal
embeddings, neither of them induces an overlapping conflict, and they cross
each other, then we say that such drawings induce an internal conflict. In
both cases, we say that the drawings of $\triangle_{i}$ and $\triangle_{j}$
conflict with each other.

We have the following.

######  Lemma 13.

Let $\triangle_{i}$ and $\triangle_{j}$ be two triangles in $L_{\triangle}$,
and $\Gamma$ be a straight-line realization of $G$ that extends $\Gamma_{F}$.
Suppose that there exists a triangle $\triangle\in\Gamma_{F}$ such that both
$\triangle_{i}$ and $\triangle_{j}$ are drawn inside $\triangle$ in $\Gamma$.
The drawings of $\triangle_{i}$ and $\triangle_{j}$ induce an internal
conflict if at least one of the following statements is true:

  1. (a)

$\triangle_{i}$ and $\triangle_{j}$ share an edge.

  2. (b)

$\sqrt{3}<r\leq 2\cos(15^{\circ})\simeq 1.93$ and $\triangle$ is a tall
isosceles triangle.

  3. (c)

$1<r\leq\sqrt{3}$.

###### Proof.

By statement (a) of Lemma 11 and since each of $\triangle_{i}$ and
$\triangle_{j}$ is drawn inside $\triangle$, the triangle $\triangle$ is
either tall isosceles or big equilateral. Furthermore, by statement (b) of
Lemma 11, each of $\triangle_{i}$ and $\triangle_{j}$ is either small
equilateral or flat isosceles. By Lemma 12, the triangles $\triangle_{i}$ and
$\triangle$ share an edge and so do $\triangle_{j}$ and $\triangle$.

Consider first the case in which $\triangle_{i}$ shares an edge with
$\triangle_{j}$, as described in statement (a). Note that, since $G$ is a
$2$-tree, the triangles $\triangle_{i}$, $\triangle_{j}$, and $\triangle$
actually share the same edge. By statement (a) of Lemma 11, $\triangle_{i}$
and $\triangle_{j}$ cannot be drawn inside each other regardless of their
types. Since $\triangle_{i}$ and $\triangle_{j}$ are drawn inside the same
triangle and they cannot be drawn inside each other, their drawings induce an
internal conflict inside $\triangle$. This proves statement (a).

Consider now the case in which $\triangle_{i}$ and $\triangle_{j}$ do not
share an edge. The triangles $\triangle_{i}$ and $\triangle_{j}$ induce an
internal conflict inside $\triangle$ depending on the types of
$\triangle_{i}$, $\triangle_{j}$, $\triangle$, and the value of $r$. Note that
$r$ is necessarily less than $2$ since, otherwise, by Property 9 both
$\triangle_{i}$ and $\triangle_{j}$ would be small equilateral triangles and
they could not share each a different side of $\triangle$, since $\triangle$
has at most one side of length $w_{1}$. By a simple geometric argument we can
deduce that two triangles are drawn inside $\triangle$ without inducing
internal conflicts in the following cases (refer to Fig. 20):

  1. (i)

If $2\cos(15^{\circ})\simeq 1.93<r<2$ and $\triangle$ is tall isosceles, then
two flat isosceles triangles and one small equilateral triangle can be drawn
inside $\triangle$ without inducing internal conflicts.

  2. (ii)

If $\sqrt{3}\simeq 1.73<r<2$ and $\triangle$ is big equilateral, then three
flat isosceles can be drawn inside $\triangle$ without inducing internal
conflicts.

The limit values $r=2\cos(15^{\circ})$ and $r=\sqrt{3}$ split the interval
$1<r<2$ into the following three intervals. First, if $2\cos(15^{\circ})<r<2$,
then the cases (i) and (ii) are both possible. Hence, $\triangle_{i}$ and
$\triangle_{j}$ can be drawn inside $\triangle$ without inducing internal
conflicts, regardless of their types. Second, if $\sqrt{3}<r\leq
2\cos(15^{\circ})$ then the case (i) is no longer possible. Hence, as
described in statement (b), $\triangle_{i}$ and $\triangle_{j}$ induce an
internal conflict inside $\triangle$ if $\triangle$ is a tall isosceles
triangle. Finally, if $1<r\leq\sqrt{3}$, then none of the cases is possible.
Hence, as described in statement (c), $\triangle_{i}$ and $\triangle_{j}$
induce an internal conflict inside $\triangle$ regardless of their types. ∎

Figure 20: Illustration for the proof of Lemma 13. The vertices that
$\triangle_{i}$ and $\triangle_{j}$ do not share with $\triangle$ lie on the
circumcenter of $\triangle$. On the left, the case in which $\triangle$ is
tall isosceles (the segments between the circumcenter of $\triangle$ and its
vertices all have the same length $l$). On the right, the case in which
$\triangle$ is big equilateral.

From Lemma 13 we obtain the following necessary condition for the existence of
a planar straight-line realization of $G$ extending $\Gamma_{F}$.

######  Lemma 14.

If there exists a planar straight-line realization of $G$, then no subset of
three triangles of $L_{\triangle}$ share a side.

###### Proof.

Suppose, for a contradiction, that there exists a planar straight-line
realization $\Gamma$ of $G$ and that three triangles of $L_{\triangle}$ share
an edge $e$. Consider two of such triangles that are on the same side of $e$
in $\Gamma$ and denote them by $\triangle_{i}$ and $\triangle_{j}$. If
$\triangle_{i}$ and $\triangle_{j}$ do not cross each other in $\Gamma$, then
they are contained one inside the other. However, this is not possible by
statement (a) of Lemma 11. ∎

If $L_{\triangle}$ satisfies the condition stated in Lemma 14, we say that
$L_{\triangle}$ is consistent.

######  Lemma 15.

If $L_{\triangle}$ is consistent, then there are $O(1)$ pairs of triangles of
$L_{\triangle}$ whose drawings induce an internal conflict inside a triangle
$\triangle\in\Gamma_{F}$.

###### Proof.

By Lemma 12, all the triangles of $L_{\triangle}$ that can be drawn inside
$\triangle$ (including those inducing an internal conflict) share an edge with
$\triangle$. By Lemma 14 and the assumed consistency of $L_{\triangle}$, there
are at most $6$ of such triangles. Hence, the drawings of at most
$\binom{6}{2}=15$ pairs of triangles can induce an internal conflict inside
$\triangle$. ∎

###  5.3 The algorithm

We are now ready to describe the algorithm to solve the FEPR problem in $O(n)$
time when the edges of $G$ can only have one of two lengths. The algorithm
consists of two stages. In the first stage, we compute the framework $G_{F}$
of $G$, and test whether $G_{F}$ admits a planar straight-line realization
$\Gamma_{F}$. Such a realization is constructed in the positive case, and the
input instance is rejected otherwise. In the second stage, we test whether
$\Gamma_{F}$ can be extended to a planar straight-line realization $\Gamma$ of
$G$, by drawing the triangles of $L_{\triangle}$ without inducing conflicts.
In the positive case, we construct and report $\Gamma$ as the desired
realization of $G$. As before, the input instance is rejected in the negative
case. We describe the algorithm in detail next.

####  5.3.1 Computing a planar straight-line realization $\Gamma_{F}$ of the
framework of $G$.

The first stage of the algorithm is formed by the following three steps.

##### Step A. Computing the framework $G_{F}$ of $G$ and the set
$L_{\triangle}$ of leaf triangles.

To compute the framework of $G$ we first choose, among all the triangles of
$G$, a triangle $\triangle_{O}$ with maximum sum of the length of its sides.
Note that $\triangle_{O}$ cannot be drawn inside any other triangle of $G$,
hence it does not belong to $L_{\triangle}$. We then compute the decomposition
tree $T$ of $G$ rooted at $\triangle_{O}$. Note that, if $G$ admits a planar
straight-line realization, then the degree of $T$ is bounded by a constant.
Indeed, each edge of $G$ can be incident to at most two interesting triangles
of the same type (and hence each $3$-cycle of $G$ can be adjacent to at most
$24$ distinct $3$-cycles). We test whether the degree of $T$ is bounded by
$24$ in $O(n)$ time. We reject the instance in the negative case. In the
positive case we traverse $T$ looking for leaf triangles that can be drawn
inside their parent or sibling triangles. By Lemma 12, these are the only
triangles in $G$ that can be drawn inside any other triangle. We identify such
triangles by means of Theorem 2.2. Since the degree of $T$ is in $O(1)$, each
triangle has a constant number of sibling triangles, hence we can compute both
$G_{F}$ and $L_{\triangle}$ in $O(n)$ time.

##### Step B. Testing if $L_{\triangle}$ is consistent.

The next step is to test if $L_{\triangle}$ is consistent. By Lemma 14, this
is a necessary condition for the existence of a planar straight-line
realization of $G$. This condition can be trivially tested in $O(n)$ time by
looking at the triangles of $L_{\triangle}$ sharing an edge with a parent or a
sibling triangle in $T$. The input instance is rejected in the negative case.

##### Step C. Constructing a planar straight-line realization $\Gamma_{F}$ of
$G_{F}$.

The final step of this stage is to compute a planar straight-line realization
of $G_{F}$, if it exists. We first test whether $G_{F}$ is outerplanar. If
this is not the case we reject the instance. Otherwise, we construct its
unique outerplane embedding in $O(n)$ time [21, 38, 50]. Then, by means of
Theorem 3.4 we test in $O(n)$ time if $G_{F}$ admits a planar straight-line
realization with the computed embedding. We construct $\Gamma_{F}$ in the
positive case, and reject the input instance otherwise.

####  5.3.2 Extending $\Gamma_{F}$ to a planar straight-line realization of
$G$.

In the second stage the algorithm distinguishes two cases, namely, the one in
which $r\geq 2$ and the one in which $r<2$. In the former case, the algorithm
is completed by means of a single step, called D.1, while in the latter case
the algorithm is completed by means of four steps, called D.2, E, F, and G.

Case $\mathbf{r}\geq 2$. Note that, by Property 9, in this case there are no
flat isosceles triangles. Hence, every leaf triangle $\triangle$ in
$L_{\triangle}$ is a small equilateral triangle such that the parent or a
sibling of $\triangle$ is a tall isosceles triangle. We act as described in
the following step.

##### Step D.1.

Consider each edge $e$ of $G_{F}$ incident to a triangle in $L_{\triangle}$.
If $e$ is incident to two triangles in $L_{\triangle}$, we draw them in
$\Gamma_{F}$ on opposite sides of $e$. If $e$ is incident to one triangle
$\triangle\in L_{\triangle}$, then we draw $\triangle$ inside any tall
isosceles triangle incident to $e$ (recall that such a tall isosceles triangle
is the parent or a sibling of $\triangle$). At the end of this process we
obtain a straight-line realization $\Gamma$ of $G$, and a plane embedding
$\mathcal{E}$ of $G$.

######  Lemma 16.

$G$ admits a planar straight-line realization if and only if $\Gamma$ is
planar.

###### Proof.

Obviously, if $\Gamma$ is planar, then it is a planar straight-line
realization of $G$.

We prove that, if $G$ admits a planar straight-line realization, then $\Gamma$
is planar. Consider an edge $e\in G_{F}$. Since $L_{\triangle}$ is consistent,
the edge $e$ is shared by a set $L^{e}_{\triangle}\subseteq L_{\triangle}$ of
at most two leaf triangles. Suppose that $e$ is an internal edge of
$\Gamma_{F}$. Then, in $\Gamma$, each small equilateral triangle
$L^{e}_{\triangle}$ is drawn as an internal embedding inside a tall isosceles
triangle $\triangle^{*}\in G_{F}$. Note that no other triangle is drawn inside
$\triangle^{*}$, since a tall isosceles triangle has a single side of length
$w_{1}$. Hence, no triangle of $L^{e}_{\triangle}$ creates a crossing in
$\Gamma$.

Suppose now that $e$ is incident to the outer face of $\Gamma_{F}$. If
$L^{e}_{\triangle}$ consists of a single triangle, then the triangle is drawn
as an internal embedding and, as above, it does not create crossings in
$\Gamma$. If $L^{e}_{\triangle}$ consists instead of two triangles, then least
one of them, say $\triangle_{s}$, is drawn as an outer embedding. However, the
two triangles in $L^{e}_{\triangle}$ are drawn on different sides of $e$ in
any planar straight-line realization of $G$, hence if $\triangle_{s}$ creates
a crossing, it does so in every straight-line realization of $G$. Since a
planar straight-line realization of $G$ exists by hypothesis, it follows that
$\triangle_{s}$ does not create crossings in $\Gamma$, and hence $\Gamma$ is
planar. ∎

Observe that $\Gamma$ and $\mathcal{E}$ are constructed in linear time. We
test whether $\Gamma$ is a planar straight-line realization of $G$ with
embedding $\mathcal{E}$ in $O(n)$ time by means of Theorem 3.1. By Lemma 16,
in the negative case we conclude that $G$ admits no planar straight-line
realization, otherwise $\Gamma$ is the desired planar straight-line
realization of $G$.

Case $\mathbf{r}<2$. The algorithm in this case is more complicated, since
there might be flat isosceles triangles in $G$, which might or might not need
to be embedded inside their adjacent large equilateral or tall isosceles
triangles in $\Gamma_{F}$. Moreover, more than a single leaf triangle might be
drawn inside the same interesting triangle of $\Gamma_{F}$.

An example of a planar straight-line realization of a weighted $2$-tree for
which $r<2$ is shown in Fig. 21. The values of $w_{1}$ and $w_{2}$ were chosen
so that $\sqrt{3}\simeq 1.73<r\leq 2\cos(15^{\circ})\simeq 1.93$. By Property
b of Lemma 13, a pair of flat isosceles triangles can be drawn inside a big
equilateral triangle without crossing each other, but any pair of interesting
triangles (either two flat isosceles or a flat isosceles and a small
equilateral) cross with each other if they are drawn inside a tall isosceles
triangle. The triangles of $\Gamma_{F}$ are drawn with thick lines, and the
edges of the leaf triangles of $L_{\triangle}$ that are not part of
$\Gamma_{F}$ are drawn with thin lines. Observe that any type of interesting
triangle can belong to the framework, whereas the triangles of $L_{\triangle}$
are either small equilateral or flat isosceles triangles. If a leaf triangle
is small equilateral, then it is adjacent to (at least) an interesting
triangle of the frame that is tall isosceles. If it is instead a flat
isosceles, then it is adjacent to (at least) an interesting triangle of the
frame that is either tall isosceles or big equilateral.

From Lemma 12, a leaf triangle can be drawn inside its parent triangle, a
sibling triangle, or both. In our example, $\triangle_{2}$ can be drawn both
inside its parent triangle $\triangle_{1}$ and inside the sibling triangle
$\triangle_{3}$. On the other hand, $\triangle_{18}$ can only be drawn inside
its parent triangle $\triangle_{17}$, and $\triangle_{21}$ can only be drawn
inside its sibling triangle $\triangle_{22}$. Consider the triangle
$\triangle_{27}$. It can only be drawn inside its parent triangle
$\triangle_{3}$ since it is congruent to its sibling triangle $\triangle_{8}$.
Hence it would induce an overlapping conflict if it were drawn on the same
side as $\triangle_{8}$. Consider now the interesting triangles drawn with
dashed lines. If $\triangle_{9}$ was drawn inside $\triangle_{17}$, then
$\triangle_{9}$ and $\triangle_{18}$ would cross each other. On the other
hand, if the drawing of $\triangle_{16}$ is an outer embedding, then it would
induce a framework conflict. Finally, if the drawings of both $\triangle_{13}$
and $\triangle_{6}$ are outer embeddings, then they would induce an external
conflict.

Figure 21:  A planar straight-line realization of a weighted $2$-tree for
$\sqrt{3}<r\leq 2\cos(15^{\circ})$. On the left, the planar straight-line
realization. Triangles in the framework are drawn with thick lines. On the
right, the decomposition tree rooted at $\triangle_{1}$.

To deal with this case we proceed as follows. First, we compute the pairs of
triangles whose drawings may induce a conflict. Then we construct a 2SAT
formula $\phi$ that contains a Boolean variable for each triangle
$\triangle\in L_{\triangle}$. The value of the variable is associated to a
choice of the two possible drawings of $\triangle$: recall that an edge of
$\triangle$ is part of $G_{F}$, while the vertex of $\triangle$ not incident
to such an edge might be placed on either side of it. For each triangle
$\triangle$ that induces a framework or an overlapping conflict in one of its
two drawings, there is a clause in $\phi$ that is True if and only if the
drawing of the triangle is not the one inducing a conflict. Similarly, for
each pair of triangles whose drawings induce an internal or an external
conflict, there is a clause in $\phi$ that is True if and only if the drawings
of the triangles are not both the ones inducing a conflict. If $\phi$ is
satisfiable, then there is a planar straight-line realization of $G$ which can
be obtained by embedding the triangles of $L_{\triangle}$ according to the
values of the variables of $\phi$. We reject the instance otherwise. We
describe the algorithm in detail next.

##### Step D.2. Detecting internal conflicts.

We start by computing all the pairs of triangles of $L_{\triangle}$ that
induce an internal conflict. This is done by traversing $T$ while processing
each triangle $\triangle\in\Gamma_{F}$ as follows. We first obtain the set
$L^{\prime}_{\triangle}\subseteq L_{\triangle}$ of leaf triangles that can be
drawn inside $\triangle$. By Lemma 12, these triangles share an edge with
$\triangle$, so they are children or siblings of $\triangle$. We then decide
which pairs of leaf triangles of $L^{\prime}_{\triangle}$ induce an internal
conflict inside $\triangle$, by means of Lemma 13. Since $L_{\triangle}$ is
consistent, by Lemma 15 there are $O(1)$ triangles in
$L^{\prime}_{\triangle}$. Hence, we process each triangle in $O(1)$ time, and
the traversal takes $O(n)$ time.

##### Step E. Detecting overlapping conflicts.

Next, for each triangle $\triangle\in L_{\triangle}$, we detect whether any of
its two drawings induces an overlapping conflict. Let $\triangle^{*}$ be the
parent of $\triangle$ in $T$ and let $e$ be the edge shared by $\triangle$ and
$\triangle^{*}$. Note that, since $\triangle\in L_{\triangle}$, one of the two
drawings of $\triangle$ lies inside $\triangle^{*}$ and hence does not induce
an overlapping conflict. We first check whether the other drawing of
$\triangle$ is an internal or an outer embedding (in the latter case, we can
conclude that $\triangle$ does not induce an overlapping conflict). This is
equivalent to checking whether there is a triangle $\triangle_{s}$ in
$\Gamma_{F}$ on the other side of $e$ with respect to $\triangle^{*}$. Note
that, if such a triangle $\triangle_{s}$ exists, then it is a sibling of
$\triangle$ in $T$, given that it shares the edge $e$ with $\triangle$ and
that it is not the parent $\triangle^{*}$ of $\triangle$. Hence, for each of
the $O(1)$ siblings of $\triangle$ in $T$, we check in $O(1)$ time whether it
is a triangle in $\Gamma_{F}$ and whether it is incident to $e$. If no sibling
of $\triangle$ in $T$ satisfies both checks, then we conclude that no drawing
of $\triangle$ induces an overlapping conflict. Otherwise, there is a sibling
of $\triangle$ in $T$ that satisfies both checks; then this sibling is the
desired triangle $\triangle_{s}$ and hence the drawing of $\triangle$ outside
$\triangle^{*}$ is an internal embedding of $\triangle$. Then we also check in
$O(1)$ time whether $\triangle_{s}$ and the drawing of $\triangle$ outside
$\triangle^{*}$ cross each other. In the positive case, we conclude that the
drawing of $\triangle$ outside $\triangle^{*}$ induces an overlapping
conflict, while in the negative case we conclude that it does not. Since we
process each triangle $\triangle\in L_{\triangle}$ in $O(1)$ time, this step
takes $O(n)$ time.

##### Step F. Detecting framework and external conflicts.

Detecting framework and external conflicts in linear time is more challenging
than overlapping and internal conflicts. Indeed, an outer embedding of a
triangle $\triangle\in L_{\triangle}$ might cross a triangle of $\Gamma_{F}$
or the outer embedding of a triangle in $L_{\triangle}$ that is far, in terms
of graph-theoretic distance, from $\triangle$. Hence, the trivial solution
would detect framework and external conflicts by comparing each triangle
$\triangle\in L_{\triangle}$ with every triangle of $\Gamma_{F}$ and with
every triangle in $L_{\triangle}$. However, this would result in a quadratic
running time. In order to achieve linear running time, we decompose the plane
into cells and then derive several combinatorial properties of such a
decomposition, including: (i) only a linear number of cells can host conflicts
and such cells can be found efficiently; (ii) conflicts can only occur between
triangles in a single cell or in adjacent cells; and (iii) each cell can host
only a constant number of outer embeddings of triangles from $L_{\triangle}$.
The last property is only true because of the assumption $r<2$. We now
describe the details of Step F.

Let $L^{\prime}_{\triangle}$ be the subset of $L_{\triangle}$ composed of
those triangles that are incident to external edges of $\Gamma_{F}$. Only the
outer embeddings of the triangles in $L^{\prime}_{\triangle}$ can induce
framework and external conflicts. We translate the Cartesian axes so that the
bottom-left corner of the bounding box of $\Gamma_{F}$ lies on the origin, and
give an outer embedding to every triangle in $L^{\prime}_{\triangle}$. This
results in a possibly non-planar straight-line realization
$\Gamma^{\prime}_{F}$ of the graph $G^{\prime}_{F}:=G_{F}\cup
L^{\prime}_{\triangle}$. Our strategy to detect external and framework
conflicts is based on the construction of a linear-size “proximity” graph $H$
defined on the vertices of $G^{\prime}_{F}$. We show that, if two triangles of
$L^{\prime}_{\triangle}$ induce an external conflict, then their vertices are
associated either with the same node or with adjacent nodes of $H$. Similarly,
if a triangle $\triangle\in L^{\prime}_{\triangle}$ induces a framework
conflict by intersecting an edge $e$ of $G^{\prime}_{F}$, then the vertices of
$\triangle$ and the end-vertices of $e$ are associated either with the same
node or with adjacent nodes of $H$. We then detect external and framework
conflicts by a linear-time traversal of $H$.

In the following, we say that a vertex of $G_{F}$ is a framework vertex and a
vertex of $L^{\prime}_{\triangle}$ that is not contained in $G_{F}$ is a leaf
vertex. For each leaf vertex $v$, we denote with $\triangle(v)$ the outer
embedding of the triangle in $L^{\prime}_{\triangle}$ whose leaf vertex is
$v$. We define the graph $H$ as follows. Consider a square grid whose cells
have side length $3w_{2}$ covering the plane; see Fig. 22. We assign a label
$l(v)=(i,j)$ to every vertex $v\in V(G^{\prime}_{F})$, where $i$ and $j$
respectively denote the row and the column of one of the (at most four) grid
cells that contain $v$ in their interior or on their boundary. More precisely,
the vertex $v$ gets the label
$(\lfloor\frac{x(v)}{3w_{2}}\rfloor,\lfloor\frac{y(v)}{3w_{2}}\rfloor)$, where
$(x(v),y(v))$ denotes the coordinates of $v$ in $\Gamma^{\prime}_{F}$. The
graph $H$ has a node for each label assigned to at least one vertex of
$G^{\prime}_{F}$, and two nodes $(i,j)$ and $(i^{\prime},j^{\prime})$ are
connected if and only if $|i-i^{\prime}|\leq 1$ and $|j-j^{\prime}|\leq 1$.
Note that $H$ has at most $n$ nodes and maximum degree 8, hence it has $O(n)$
edges. We say that a vertex of $G^{\prime}_{F}$ is associated with a node
$\mu$ of $H$ if $\mu$ represents the cell $(i,j)$ and $l(v)=(i,j)$.

Figure 22:  On the left, the straight-line realization $\Gamma^{\prime}_{F}$
of the graph $G^{\prime}_{F}:=G_{F}\cup L^{\prime}_{\triangle}$, where each
triangle in $L^{\prime}_{\triangle}$ has an outer embedding. The triangles of
$G_{F}$ are shown in gray, and the outer embeddings of the triangles in
$L^{\prime}_{\triangle}$ are shown in white. Framework vertices are shown in
white and leaf vertices are shown in blue. The grid cell filled with dashed
lines is zoomed-in on the right. All the triangles in $L^{\prime}_{\triangle}$
contained in this cell can induce external or framework conflicts only with
the triangles contained in the nine highlighted cells.

######  Lemma 17.

The graph $H$ satisfies the following properties:

  1. (a)

For each node $\mu$ of $H$, there are $O(1)$ leaf vertices associated with
$\mu$.

  2. (b)

Let $\triangle_{1},\triangle_{2}$ be two triangles in
$L^{\prime}_{\triangle}$. For $i=1,2$, let $\mu_{i}$ denote a node of $H$ such
that at least one vertex of $\triangle_{i}$ is associated with $\mu$. If the
outer embeddings of $\triangle_{1}$ and $\triangle_{2}$ induce an external
conflict, then either $\mu_{1}=\mu_{2}$ or $(\mu_{1},\mu_{2})\in E(H)$.

  3. (c)

Let $\triangle$ be a triangle in $L^{\prime}_{\triangle}$, and $e$ be an edge
of $G_{F}$ incident to the outer face of $\Gamma_{F}$. Let $\mu$ and $\nu$
denote two nodes of $H$ such that at least one vertex of $\triangle$ is
associated with $\mu$ and at least one end-vertex of $e$ is associated with
$\nu$. If the outer embedding of $\triangle$ induces a framework conflict by
intersecting $e$, then either $\mu_{1}=\mu_{2}$ or $(\mu_{1},\mu_{2})\in
E(H)$.

###### Proof.

Consider any leaf vertex $v$ associated with a node $\mu$ of $H$. Let $(i,j)$
be the cell corresponding to $\mu$ and $\triangle$ be the parent triangle of
the triangle in $L^{\prime}_{\triangle}$ that has $v$ as a vertex. By
statement (b) of Lemma 11, we have that $\triangle$ is either a big
equilateral or a tall isosceles triangle. Further, $\triangle$ is contained in
the union of the nine cells $(i^{\prime},j^{\prime})$ for $|i-i^{\prime}|\leq
1$ and $|j-j^{\prime}|\leq 1$ (see the highlighted cells in Fig. 22); this is
because the Euclidean distance between $v$ and every point of $\triangle$ is
smaller than $2w_{2}$, while the side length of a grid cell is $3w_{2}$.
Observe that the area of a big equilateral or tall isosceles triangle is
larger than the area of a small equilateral triangle, which is equal to
$w_{1}^{2}\sqrt{3}/4$. Moreover, any two parent triangles are interior-
disjoint in $\Gamma^{\prime}_{F}$. Since the area of the union of the nine
cells is $81w_{2}^{2}$, then at most
$81w_{2}^{2}\frac{4}{w_{1}^{2}\sqrt{3}}=\frac{324}{\sqrt{3}}\left(\frac{w_{2}}{w_{1}}\right)^{2}\in
O(r^{2})$ parent triangles are contained in the nine cells, and $O(r^{2})$
leaf vertices are associated with $\mu$. Since $r<2$, we have $O(r^{2})\in
O(1)$. This proves Property (a).

To prove Property (b), suppose, for the sake of contradiction, that the outer
embeddings of $\triangle_{1}$ and $\triangle_{2}$ induce an external conflict,
with $\mu_{1}\neq\mu_{2}$ and $(\mu_{1},\mu_{2})\notin E(H)$. Since
$\triangle_{1}$ and $\triangle_{2}$ induce an external conflict, then there is
at least a point $x$ in $\triangle_{1}\cap\triangle_{2}$. Note that $x$ is at
distance smaller than or equal to $w_{2}$ from the vertices of $\triangle_{1}$
and $\triangle_{2}$, which implies that every vertex of $\triangle_{1}$ is at
distance smaller than or equal to $2w_{2}$ from any vertex of $\triangle_{2}$.
Since there is a distance larger than or equal to $3w_{2}$ between two
vertices of $G^{\prime}_{F}$ associated to non-adjacent nodes of $H$, then
either $\mu_{1}=\mu_{2}$ or $(\mu_{2},\mu_{2})\in E(H)$, which is a
contradiction.

Finally, Property (c) can be proved by similar arguments to those we used to
prove Property (b). ∎

In order to detect external and framework conflicts, we define each node $\mu$
of $H$ representing the cell $(i,j)$ as a record storing (i) a label
$l(\mu)=(i,j)$ and (ii) a list $L(\mu)$ that contains the vertices of
$G^{\prime}_{F}$ associated with $\mu$. We next describe an efficient
algorithm to construct $H$.

######  Lemma 18.

The graph $H$ can be constructed in $O(n)$ time.

###### Proof.

We first show how to construct the vertex set $V(H)$ of $H$.

Consider a total order $\pi$ of the vertices of $G^{\prime}_{F}$ such that,
for any two vertices $u$ and $v$ with $l(u)=(i_{u},j_{u})$ and
$l(v)=(i_{v},j_{v})$, it holds that $u$ precedes $v$ in the order if (i)
$i_{u}<i_{v}$ or (ii) $i_{u}=i_{v}$ and $j_{u}<j_{v}$; if $i_{u}=i_{v}$ and
$j_{u}=j_{v}$, then $u$ and $v$ are in any relative order in $\pi$. Since
$G^{\prime}_{F}$ is connected and any edge of $G^{\prime}_{F}$ has length at
most $w_{2}$, then $i,j\leq\frac{w_{2}n}{3w_{2}}=\frac{1}{3}n$ for any label
$(i,j)$. Hence, we can compute $\pi$ in $O(n)$ time by means of counting sort.

We process the vertices of $G^{\prime}_{F}$ in the order in which they appear
in $\pi$. Let $s$ be the first vertex in the order $\pi$. We create a node
$\nu$ of $H$, set $l(\nu)=l(s)$, and add $s$ to $L(\nu)$. Let now $v$ be the
currently considered vertex of $\pi$ and let us denote by $\mu$ the last
created node of $H$. If $l(v)=l(\mu)$, then we add $v$ to $L(\mu)$; otherwise,
we create a node $\mu^{\prime}$ of $H$, set $l(\mu^{\prime})=l(v)$, and add
$v$ to $L(\mu^{\prime})$. Note that, if two vertices of $G^{\prime}_{F}$ have
the same label, then they are consecutive in $\pi$. Therefore, the above
procedure creates a new node of $H$ for each label of a vertex of
$G^{\prime}_{F}$, and vertices with the same label $(i,j)$ are all placed in
the list $L(\mu)$ of the node $\mu$ such that $l(\mu)=(i,j)$. The procedure
can clearly be performed in overall $O(n)$ time.

We now show how to construct the edge set $E(H)$ of $H$.

We define a partition of $E(H)$ into four subsets
$E_{-},E_{|},E_{/},E_{\backslash}$; refer to Fig. 23. Consider any edge
$(\mu,\nu)\in E(H)$, where we denote $l(\mu)=(i_{\mu},j_{\mu})$ and
$l(\nu)=(i_{\nu},j_{\nu})$. Then $(\mu,\nu)$ belongs to $E_{-}$, $E_{|}$,
$E_{/}$, or $E_{\backslash}$, depending on whether $(\mu,\nu)$ satisfies
Property $P_{-}$, $P_{|}$, $P_{/}$, or $P_{\backslash}$, respectively, where:

$P_{-}$:

$i_{\mu}=i_{\nu}$ and $|j_{\mu}-j_{\nu}|=1$,

$P_{|}$:

$j_{\mu}=j_{\nu}$ and $|i_{\mu}-i_{\nu}|=1$,

$P_{/}$:

either $i_{\mu}-i_{\nu}=j_{\mu}-j_{\nu}=1$ or
$i_{\mu}-i_{\nu}=j_{\mu}-j_{\nu}=-1$, and

$P_{\backslash}$:

either $i_{\mu}-i_{\nu}=1$ and $j_{\mu}-j_{\nu}=-1$ or $i_{\mu}-i_{\nu}=-1$
and $j_{\mu}-j_{\nu}=1$.

Figure 23:  Construction of the set of edges $E(H)$. The edges on the sets
$E_{-},E_{|},E_{/}$, and $E_{\backslash}$ are shown in yellow, blue, green,
and red, respectively.

In order to construct the sets $E_{-},E_{|},E_{/}$, and $E_{\backslash}$, we
define four total orders $\pi_{-}$, $\pi_{|}$, $\pi_{/}$, and
$\pi_{\backslash}$ of the nodes of $H$, respectively. For any two nodes $\mu$
and $\nu$ of $H$, it holds that $\mu$ precedes $\nu$ in $\pi_{-}$, $\pi_{|}$,
$\pi_{/}$, and $\pi_{\backslash}$ if and only if the following conditions
hold, respectively:

$C_{-}$:

either $i_{\mu}<i_{\nu}$ or $i_{\mu}=i_{\nu}$ and $j_{\mu}<j_{\nu}$,

$C_{|}$:

either $j_{\mu}<j_{\nu}$ or $j_{\mu}=j_{\nu}$ and $i_{\mu}<i_{\nu}$,

$C_{/}$:

either $i_{\mu}-j_{\mu}<i_{\nu}-j_{\nu}$ or $i_{\mu}-j_{\mu}=i_{\nu}-j_{\nu}$
and $i_{\mu}<i_{\nu}$, or

$C_{\backslash}$:

either $i_{\mu}+j_{\mu}<i_{\nu}+j_{\nu}$ or $i_{\mu}+j_{\mu}=i_{\nu}+j_{\nu}$
and $i_{\mu}<i_{\nu}$.

We construct the set $E_{i}$ with $i\in\\{-,|,/,\backslash\\}$ as follows.
First, we compute the total order $\pi_{i}$ of the nodes of $H$ for which
condition $C_{i}$ holds for any pair $(\mu,\nu)$ of nodes such that $\mu$
precedes $\nu$ in $\pi_{i}$. Similarly as in the construction of $\pi$, the
order $\pi_{i}$ can be computed in $O(n)$ time by means of counting sort. Then
we process the nodes of $V(H)$ in the order $\pi_{i}$ and add a new edge
$(\mu,\nu)$ to $E_{i}$ whenever condition $P_{i}$ holds for two nodes $\mu$
and $\nu$ such that $\mu$ immediately precedes $\nu$ in $\pi_{i}$. Since, by
construction, nodes that are adjacent in $E_{i}$ are consecutive in $\pi_{i}$,
it follows that the above procedure correctly computes each set $E_{i}$.
Clearly, the procedure can be performed in overall $O(n)$ time. This concludes
the construction of $H$. ∎

We now describe an algorithm, which we call ConflictFinder, to detect external
and framework conflicts. Broadly speaking, the algorithm performs two linear-
time traversals of the edges of $H$. In the first traversal, we detect
external conflicts. When processing the edge $(\mu,\nu)\in E(H)$ we detect
intersections between the triangles of $L^{\prime}_{\triangle}$ whose leaf
vertices are contained in $L(\mu)\cup L(\nu)$. In the second traversal, we
detect framework conflicts. In this case, when processing the edge
$(\mu,\nu)\in E(H)$ we detect intersections between the triangles of
$L^{\prime}_{\triangle}$ and the edges of $G^{\prime}_{F}$ whose leaf and
framework end-vertices, respectively, are contained in $L(\mu)\cup L(\nu)$.

The algorithm consists of the following steps:

  1. Step 1:

Compute the drawing $\Gamma^{\prime}_{F}$ of $G^{\prime}_{F}$ and the
auxiliary graph $H$ as described above.

  2. Step 2:

For every framework vertex $v$, create the list $L_{E}(v)$ of the two edges of
$\Gamma_{F}$ incident to both $v$ and the outer face of $\Gamma_{F}$.

  3. Step 3:

For every node $\mu\in V(H)$, create the lists $L_{\ell}(\mu)$ and
$L_{F}(\mu)$ of leaf and framework vertices contained in $L(\mu)$,
respectively.

  4. Step 4:

Detect which triangles of $L^{\prime}_{\triangle}$ induce external conflicts
as follows. Let $\mathcal{E}_{\ell}=\\{(u,v)\in
L_{\ell}(\mu)\times\\{L_{\ell}(\mu)\cup L_{\ell}(\nu)\\}\,|\,(\mu,\nu)\in
E(H)\\}$. For every pair of vertices $(u,v)\in\mathcal{E}_{\ell}$, test if
$\triangle(u)$ and $\triangle(v)$ intersect each other. In the positive case,
the triangles $\triangle(u)$ and $\triangle(v)$ induce an external conflict.

  5. Step 5:

Detect which triangles of $L^{\prime}_{\triangle}$ induce framework conflicts
as follows. Let $\mathcal{E}_{F}=\\{(u,v)\in
L_{F}(\mu)\times\\{L_{\ell}(\mu)\cup L_{\ell}(\nu)\\}\,|\,(\mu,\nu)\in
E(H)\\}$. For every pair of vertices $(u,v)\in\mathcal{E}_{F}$, test if there
is an edge $e\in L_{E}(u)$ such that $e$ intersects $\triangle(v)$. In the
positive case, the triangle $\triangle(v)$ induces a framework conflict with
the edge $e$.

The correctness and complexity of the algorithm are proved in the following
lemma.

######  Lemma 19.

The algorithm ConflictFinder detects all the external and framework conflicts
in $O(n)$ time.

###### Proof.

We first prove the correctness of the algorithm. Consider first the detection
of external conflicts. Let $u$ and $v$ be two leaf vertices associated
respectively to two nodes $\mu$ and $\nu$. Remember that $\triangle(u)$ and
$\triangle(v)$ induce an external conflict if and only if they intersect each
other. Then, by Property (b) of Lemma 17, we have that either $\mu=\nu$ or
$(\mu,\nu)\in E(H)$. Since in Step 4 the algorithm processes each pair of leaf
triangles whose leaf vertices are associated with the same node of $H$ or with
adjacent nodes of $H$, it follows that all the external conflicts are being
detected.

Consider now the detection of framework conflicts. Let $u$ be a framework
vertex associated to a node $\mu$, let $v$ be a leaf vertex associated to a
node $\nu$, and $e$ be an edge in $L_{E}(u)$. Remember that $\triangle(v)$
induces a framework conflict with $e$ if and only if $\triangle(v)$ and $e$
intersect each other. Then, by Property (c) of Lemma 17, we have that either
$\mu=\nu$ or $(\mu,\nu)\in E(H)$. Since in Step 5 the algorithm processes each
pair composed of a framework and a leaf vertex that are associated either with
the same node of $H$ or with adjacent nodes of $H$, it follows that all the
framework conflicts are being detected.

We now bound the time complexity of the algorithm. This is done by bounding
the time complexity of each of the Steps 1–5.

  * •

Since there are $O(n)$ triangles in $L^{\prime}_{\triangle}$, we have that
$\Gamma_{F}$ can be extended to $\Gamma^{\prime}_{F}$ in $O(n)$ time.
Furthermore, the graph $H$ can be computed in $O(n)$ time by Lemma 18. Hence
Step 1 takes $O(n)$ time.

  * •

Step 2 takes $O(n)$ time since the boundary of the outer face of $\Gamma_{F}$
consists of $O(n)$ line segments.

  * •

Step 3 takes also $O(n)$ time, since $H$ has at most $n$ nodes, and every
vertex $v$ of $G^{\prime}_{F}$ is contained in the list $L(\mu)$ of a single
node $\mu$ of $H$.

  * •

The time complexity of Step 4 is bounded by $O(|\mathcal{E}_{\ell}|)$. Note
that $H$ contains $O(n)$ edges; moreover, for every node $\mu$ of $H$, the
list $L_{\ell}(\mu)$ contains $O(1)$ leaf vertices, by Property (a) of Lemma
17. Hence $\mathcal{E}_{\ell}$ contains $O(n)$ pairs of vertices and Step 4
takes $O(n)$ time.

  * •

Finally, the time complexity of Step 5 is bounded by $O(|\mathcal{E}_{F}|)$.
In this case, even though $\Theta(n)$ framework vertices might be associated
with the same node of $H$, each framework vertex appears in $O(1)$ pairs of
$\mathcal{E}_{F}$; namely, if a framework vertex $u$ is associated with a node
$\mu$ of $H$, then it only appears in the pairs $(u,v)$ of $\mathcal{E}_{F}$
such that the leaf vertex $v$ is associated either with $\mu$ or with one of
the (at most $8$) neighbors of $\mu$ in $H$. By Property (a) of Lemma 17,
there are $O(1)$ leaf vertices associated with the same node of $H$, hence
$\mathcal{E}_{F}$ contains $O(n)$ pairs of vertices and Step 5 takes $O(n)$
time.

This concludes the proof of the time complexity and hence the proof of the
lemma. ∎

##### Step G. Extending $\Gamma_{F}$ to a planar straight-line realization of
$G$.

The final step is to draw the triangles of $L_{\triangle}$ in $\Gamma_{F}$
without inducing conflicts, so that the resulting drawing remains planar. We
decide if this is possible by means of a 2SAT formula. Each leaf triangle
$\triangle_{i}\in L_{\triangle}$ can have two embeddings (which differ from
each other for the position of the leaf vertex of $\triangle_{i}$). We
arbitrarily associate each embedding with a distinct truth value of a suitable
Boolean variable, and construct the clauses of the formula as follows:

  * •

If a drawing of $\triangle_{i}$ induces an overlapping conflict, then we
introduce a clause $(\neg\ell_{i})$, where $\ell_{i}$ is the literal that is
True when $\triangle_{i}$ has the drawing that induces an overlapping
conflict.

  * •

If $\triangle_{i}$ induces a framework conflict, we introduce a clause
$(\neg\ell_{i})$, where $\ell_{i}$ is the literal that is True when
$\triangle_{i}$ has an outer embedding.

  * •

If two leaf triangles $\triangle_{i},\triangle_{j}\in L_{\triangle}$ induce an
internal conflict inside a triangle $\triangle\in\Gamma_{F}$, we introduce a
clause $(\neg\ell_{i}\vee\neg\ell_{j})$, where $\ell_{i}$ (resp. $\ell_{j}$)
is the literal that is True when $\triangle_{i}$ (resp. $\triangle_{j}$) is
drawn inside $\triangle$.

  * •

If two leaf triangles $\triangle_{i},\triangle_{j}\in L_{\triangle}$ induce an
external conflict, we introduce a clause $(\neg\ell_{i}\vee\neg\ell_{j})$,
where $\ell_{i}$ (resp. $\ell_{j}$) is the literal that is True when
$\triangle_{i}$ (resp. $\triangle_{j}$) has an outer embedding.

Let $\phi$ be the 2SAT formula produced by the clauses introduced as described
above. Clearly, the clauses of $\phi$ describe all and only the overlapping,
framework, internal, and external conflicts defined in Section 5.2. Moreover,
since there are $O(n)$ triangles in $L_{\triangle}$, the number of framework
and overlapping conflicts is in $O(n)$. Further, since $H$ has $O(n)$ vertices
and edges, by Lemmas 15 and 17 the number of internal and external conflicts
is in $O(n)$, respectively. It follows that $\phi$ contains $O(n)$ clauses.
The following lemma shows that a solution to $\phi$ corresponds to a planar
straight-line realization of $G$.

######  Lemma 20.

The formula $\phi$ is satisfiable if and only if $\Gamma_{F}$ can be extended
to a planar straight-line realization of $G$. Also, if $\phi$ is satisfiable,
then such a planar straight-line realization can be constructed in $O(n)$
time.

###### Proof.

We prove the two directions separately.

$(\Longrightarrow)$ Assume that $\phi$ is satisfiable. We show that
$\Gamma_{F}$ can be extended to a planar straight-line realization of $G$.
Consider a truth assignment for the Boolean variables that satisfies $\phi$.
The variables of $\phi$ are in one to one correspondence with the triangles of
$L_{\triangle}$. We draw in $\Gamma_{F}$ each triangle $\triangle_{i}\in
L_{\triangle}$ with the embedding associated with the truth value of the
variable corresponding to $\triangle_{i}$ in the satisfying assignment for
$\phi$. This can clearly be done in $O(1)$ time per triangle in
$L_{\triangle}$, hence in overall $O(n)$ time. Since each clause of $\phi$ is
satisfied, it follows that $\triangle_{i}$ is drawn in $\Gamma_{F}$ without
inducing conflicts. Since this is true for every $\triangle_{i}\in
L_{\triangle}$, it follows that the resulting straight-line realization of $G$
is planar. Furthermore, such a realization can be constructed in $O(n)$ time
since there are $O(n)$ clauses in $\phi$.

$(\Longleftarrow)$ Let $\Gamma$ be a planar straight-line realization of $G$.
We show that $\phi$ is satisfiable. The embedding in $\Gamma$ of each triangle
$\triangle_{i}\in L_{\triangle}$ identifies a truth value for the
corresponding variable in $\phi$, and thus, a truth assignment for $\phi$.
Such an assignment satisfies $\phi$ since an unsatisfied clause would imply
that we have either an overlapping, or a framework, or an internal, or an
external conflict, which in turn implies that the boundary of some triangle
$\triangle_{i}\in L_{\triangle}$ crosses the boundary of a triangle of
$\Gamma_{F}$ or the boundary of another triangle of $L_{\triangle}$,
contradicting the fact that $\Gamma$ is planar. This concludes the proof. ∎

By the discussion in Steps D.2, E, and F, we have that $\phi$ can be
constructed in $O(n)$ time. Further, as argued above, $\phi$ contains $O(n)$
clauses. We can therefore test whether $\phi$ is satisfiable in $O(n)$ time
[6]. If $\phi$ is not satisfiable, we reject the instance. Otherwise, we
extend $\Gamma_{F}$ to a planar straight-line realization of $G$ in $O(n)$
time as described in the proof of Lemma 20. This concludes the proof of
Theorem 5.2.

##  6 Maximal Outerplanar Graphs

In this section we study the FEPR problem for weighted outerplanar $2$-trees,
that is, for weighted maximal outerplanar graphs. While we could not establish
the computational complexity of the FEPR problem for general maximal
outerplanar graphs, we can prove the following two theorems.

######  Theorem 6.1.

Let $G$ be an $n$-vertex weighted maximal outerpath. There exists an
$O(n)$-time algorithm that tests whether $G$ admits a planar straight-line
realization and, in the positive case, constructs such a realization.

######  Theorem 6.2.

Let $G$ be an $n$-vertex weighted maximal outerpillar. There exists an
$O(n^{3})$-time algorithm that tests whether $G$ admits a planar straight-line
realization and, in the positive case, constructs such a realization.

(a) (b) (c)

Figure 24: (a) and (b) show two $e$-outer realizations $\Gamma$ and
$\Gamma^{\prime}$ of a weighted $2$-tree. The gray regions show
$\mathcal{I}_{\Gamma}$ and $\mathcal{I}_{\Gamma^{\prime}}$. We have that
$\Gamma$ is $e$-smaller than $\Gamma^{\prime}$. Indeed, as shown in (c),
$\Gamma$ can be rotated, translated, and reflected so that the representation
of $e$ coincides with the one in $\Gamma^{\prime}$ and so that its interior is
a subset of the interior of $\Gamma^{\prime}$.

Before proving Theorems 6.1 and 6.2, we establish some notation and
definitions that are common to both proofs. Let $G$ be a weighted $2$-tree.
For a planar straight-line realization $\Gamma$ of $G$, the interior of
$\Gamma$, denoted by $\mathcal{I}_{\Gamma}$, is the complement of the outer
face of $\Gamma$, i.e., the union of the closure of the internal faces of
$\Gamma$. Let $e$ be an edge of $G$. An $e$-outer realization of $G$ is a
planar straight-line realization of $G$ such that $e$ is incident to its outer
face. Given two $e$-outer realizations $\Gamma$ and $\Gamma^{\prime}$ of $G$,
we say that $\Gamma$ is $e$-smaller than $\Gamma^{\prime}$ if there exists an
$e$-outer realization $\Gamma^{\prime\prime}$ that can be obtained by a rigid
transformation of $\Gamma$ such that the end-vertices of $e$ lie at the same
points in $\Gamma^{\prime\prime}$ and in $\Gamma^{\prime}$ and such that
$\mathcal{I}_{\Gamma^{\prime\prime}}\subseteq\mathcal{I}_{\Gamma^{\prime}}$
(see Fig. 24); that is $\Gamma$ is $e$-smaller than $\Gamma^{\prime}$ if it
can be rotated, translated, and possibly reflected so that the representation
of $e$ coincides with the one in $\Gamma^{\prime}$ and so that its interior is
a subset of the interior of $\Gamma^{\prime}$. A set $\mathcal{R}$ of
$e$-outer realizations of $G$ is $e$-optimal if, for every $e$-outer
realization $\Gamma^{\prime}$ of $G$, there exists an $e$-outer realization
$\Gamma$ of $G$ in $\mathcal{R}$ such that $\Gamma$ is $e$-smaller than
$\Gamma^{\prime}$. An $e$-outer realization $\Gamma$ of $G$ is $e$-optimal if
the set $\\{\Gamma\\}$ is $e$-optimal.

The following lemma will be very useful; see Fig. 25. Roughly speaking, it
asserts that, in order to construct a planar straight-line realization of a
weighted $2$-tree, for certain subgraphs it is not a loss of generality to use
realizations that are “as $e$-small as possible”.

######  Lemma 21.

Let $G$ be a weighted $2$-tree that admits a planar straight-line realization
$\mathcal{G}$. Let $H$ and $K$ be two subgraphs of $G$ that satisfy the
following properties:

  * •

$H$ and $K$ are weighted $2$-trees;

  * •

$H\cup K=G$ (that is, every vertex and edge of $G$ is in $H$ or in $K$);

  * •

$H\cap K=e$ (that is, $H$ and $K$ share an edge $e$, the end-vertices of $e$,
and no other edge or vertex);

  * •

the restriction $\mathcal{H}$ of $\mathcal{G}$ to $H$ is an $e$-outer
realization of $H$; and

  * •

no vertex of $K$ lies inside an internal face of $\mathcal{H}$ in
$\mathcal{G}$.

Let $\mathcal{H}^{\prime}$ be any $e$-outer realization of $H$ that is
$e$-smaller than $\mathcal{H}$. Then it is possible to replace $\mathcal{H}$
with an $e$-outer realization of $H$ that can be obtained by a rigid
transformation of $\mathcal{H}^{\prime}$ in such a way that the resulting
straight-line realization of $G$ is planar.

(a) (b)

Figure 25: (a) The drawing $\mathcal{G}$; the set $\mathcal{I}_{\mathcal{H}}$
is shaded gray. The region with dark gray strips is the face $f$ of
$\mathcal{K}$. (b) The drawing obtained from $\mathcal{G}$ by replacing
$\mathcal{H}$ with $\mathcal{H}^{\prime\prime}$; the set
$\mathcal{I}_{\mathcal{H}^{\prime\prime}}$ is gray.

###### Proof.

Let $\mathcal{K}$ be the restriction of $\mathcal{G}$ to $K$. Assume that $H$
has more than two vertices, as otherwise $H$ contains a single edge, hence
$\mathcal{H}^{\prime}$ can be obtained by a rigid transformation of
$\mathcal{H}$ and the statement is trivial. By assumption, no vertex of $K$
lies in $\mathcal{I}_{\mathcal{H}}$; further, $H$ is biconnected, by Property
(P1) of a $2$-tree. It follows that there is a face $f$ of $\mathcal{K}$ that
contains $\mathcal{H}$ entirely, except for the edge $e$ and its end-vertices,
which are shared by $H$ and $K$. By assumption, there exists an $e$-outer
realization $\mathcal{H}^{\prime\prime}$ of $H$ that can be obtained by a
rigid transformation of $\mathcal{H}^{\prime}$ such that
$\mathcal{I}_{\mathcal{H}^{\prime\prime}}\subseteq\mathcal{I}_{\mathcal{H}}$,
hence the part of $\mathcal{H}^{\prime\prime}$ different from the edge $e$
does not intersect $\mathcal{K}$; the edge $e$ does not intersect
$\mathcal{K}$ either, as it is part of it and $\mathcal{K}$ is planar. Hence,
the straight-line realization of $G$ resulting from the replacement of
$\mathcal{H}$ with $\mathcal{H}^{\prime\prime}$ in $\mathcal{G}$ is planar. ∎

We are now ready to prove Theorems 6.1 and 6.2.

Proof of Theorem 6.1. Let $G=(V,E,\lambda)$ be an $n$-vertex weighted maximal
outerpath (as the one in Fig. 26) and let $\mathcal{O}$ be its outerplane
embedding, which can be found in $O(n)$ time [21, 38, 50]. Since $G$ is an
outerpath, its dual tree is a path, which we denote by
$P:=(p_{1},\dots,p_{k})$, where $k=n-2$; note that $P$ can be easily recovered
from $\mathcal{O}$ in $O(n)$ time. Each node $p_{i}$ of $P$ corresponds to an
internal face of $\mathcal{O}$; we denote by $c_{i}$ the $3$-cycle of $G$
bounding such a face; each cycle $c_{i}$ has a unique (planar) straight-line
realization (up to a rigid transformation), which we denote by
$\mathcal{C}_{i}$. Further, for $i=1,\dots,k-1$, let $e_{i}$ be the edge of
$G$ that is dual to the edge $(p_{i},p_{i+1})$ of $P$; note that $e_{i}$ is an
internal edge of $\mathcal{O}$.

Figure 26: The outerplane embedding of an outerpath. The gray face is the one
bounded by $c_{x}$. The graphs $G_{1}$ and $G_{2}$ are enclosed inside fat
curves.

Let $x\in\\{1,\dots,k\\}$ be an index such that the sum of the lengths of the
edges of $c_{x}$ is maximum. Let $G_{1}$ be the subgraph of $G$ composed of
the $3$-cycles $c_{1},c_{2},\dots,c_{x-1}$ and let $G_{2}$ be the subgraph of
$G$ composed of the $3$-cycles $c_{x+1},c_{x+2},\dots,c_{k}$. One of these
graphs might be undefined if $x=1$ or $x=k$; however, in the following, we
assume that $1<x<k$ as the arguments for the cases $x=1$ and $x=k$ are
analogous and actually simpler. Note that $G_{1}$ and $G_{2}$ are maximal
outerpaths.

Assume that a planar straight-line realization $\Gamma$ of $G$ exists; for
$i=1,2$, let $\Gamma_{i}$ be the restriction of $\Gamma$ to $G_{i}$. Since the
sum of the lengths of the edges of $c_{x}$ is maximum among all the $3$-cycles
of $G$, it follows that $c_{x}$ does not lie inside any $3$-cycle of $G$ in
$\Gamma$; hence, $\Gamma_{1}$ is an $e_{x-1}$-outer realization of $G_{1}$ and
$\Gamma_{2}$ is an $e_{x}$-outer realization of $G_{2}$.

A key ingredient of our algorithm is the fact that, if there exists an
$e_{x-1}$-outer realization of $G_{1}$ (resp. an $e_{x}$-outer realization of
$G_{2}$), then there exists an $e_{x-1}$-optimal realization of $G_{1}$ (resp.
an $e_{x}$-optimal realization of $G_{2}$). Indeed, in the following, we show
an $O(n)$-time algorithm that either (i) concludes that $G_{1}$ admits no
$e_{x-1}$-outer realization or that $G_{2}$ admits no $e_{x}$-outer
realization, and thus $G$ admits no planar straight-line realization, or (ii)
constructs an $e_{x-1}$-optimal realization $\Gamma_{1}$ of $G_{1}$ and its
plane embedding $\mathcal{E}(\Gamma_{1})$, and an $e_{x}$-optimal realization
$\Gamma_{2}$ of $G_{2}$ and its plane embedding $\mathcal{E}(\Gamma_{2})$.

Figure 27: The four different ways to combine $\Gamma_{1}$ and $\Gamma_{2}$
with $\mathcal{C}_{x}$. In this example, the first realization is not planar,
while the other three are.

In view of the argument above, the existence of such an algorithm suffices to
conclude the proof of the theorem. Indeed, if the algorithm concludes that
$G_{1}$ admits no $e_{x-1}$-outer realization or that $G_{2}$ admits no
$e_{x}$-outer realization, then $G$ admits no planar straight-line
realization. Otherwise, the algorithm constructs an $e_{x-1}$-optimal
realization $\Gamma_{1}$ of $G_{1}$, together with its plane embedding
$\mathcal{E}(\Gamma_{1})$, and an $e_{x}$-optimal realization $\Gamma_{2}$ of
$G_{2}$, together with its plane embedding $\mathcal{E}(\Gamma_{2})$. Then, in
order to test whether $G$ admits a planar straight-line realization, we
consider the unique (up to a rigid transformation) planar straight-line
realization $\mathcal{C}_{x}$ of $c_{x}$ and we try to combine it with
$\Gamma_{1}$ and $\Gamma_{2}$ (see Fig. 27). This combination can be done in
four ways. Indeed, once $\Gamma_{1}$ and $\mathcal{C}_{x}$ coincide on the
representation of $e_{x-1}$, it still remains to decide whether the vertex of
$c_{x-1}$ not incident to $e_{x-1}$ and the vertex of $c_{x}$ not incident to
$e_{x-1}$ lie on different sides or on the same side of the line through
$e_{x-1}$, and similarly for $\Gamma_{2}$ and $\mathcal{C}_{x}$. These two
independent choices result in four straight-line realizations of $G$. Each of
these realizations, say $\Gamma$, can be constructed in $O(n)$ time; further,
its plane embedding $\mathcal{E}(\Gamma)$ can also be constructed in $O(n)$
time from $\mathcal{E}(\Gamma_{1})$ and $\mathcal{E}(\Gamma_{2})$. Then it can
be tested in $O(n)$ time whether $\Gamma$ is a planar straight-line
realization respecting $\mathcal{E}(\Gamma)$, due to Theorem 3.1. If (at
least) one of the four realizations is planar, then it is the desired planar
straight-line realization of $G$. Otherwise, we claim that there exists no
planar straight-line realization of $G$. For a contradiction, assume that
there exists such a realization, and denote it by $\Gamma$. Since $\Gamma_{1}$
is $e_{x-1}$-optimal, it is $e_{x-1}$-smaller than the restriction of $\Gamma$
to $G_{1}$; hence, we can apply Lemma 21 with $H=G_{1}$, $K=G_{2}\cup c_{x}$,
$\mathcal{G}=\Gamma$, $e=e_{x-1}$, and $\mathcal{H}^{\prime}=\Gamma_{1}$, in
order to obtain a planar straight-line realization $\Gamma^{\prime}$ of $G$
whose restriction to $G_{1}$ is $\Gamma_{1}$. Further, since $\Gamma_{2}$ is
$e_{x}$-optimal, it is $e_{x}$-smaller than the restriction of
$\Gamma^{\prime}$ to $G_{2}$; hence, we can apply Lemma 21 with $H=G_{2}$,
$K=G_{1}\cup c_{x}$, $\mathcal{G}=\Gamma^{\prime}$, $e=e_{x}$, and
$\mathcal{H}^{\prime}=\Gamma_{2}$, in order to obtain a planar straight-line
realization $\Gamma^{\prime\prime}$ of $G$ whose restriction to $G_{1}$ is
$\Gamma_{1}$ and whose restriction to $G_{2}$ is $\Gamma_{2}$; however, this
is one of the four straight-line realizations for which the planarity testing
was negative, a contradiction.

It remains show an $O(n)$-time algorithm that either concludes that $G_{1}$
admits no $e_{x-1}$-outer realization, or determines an $e_{x-1}$-optimal
realization of $G_{1}$. A very similar application of the algorithm allows us
to either conclude that $G_{2}$ admits no $e_{x}$-outer realization or to
determine an $e_{x}$-optimal realization of $G_{2}$.

For $i=1,\dots,x-1$, let $G^{i}_{1}$ be the subgraph of $G_{1}$ composed of
the $3$-cycles $c_{1},c_{2},\dots,c_{i}$; note that $G^{x-1}_{1}=G_{1}$. A key
observation for our algorithm is the following. Assume that an $e_{x-1}$-outer
realization $\Gamma_{1}$ of $G_{1}$ exists; let $\Gamma^{i}_{1}$ be the
restriction of $\Gamma_{1}$ to $G^{i}_{1}$. Then $\Gamma^{i}_{1}$ is an
$e_{i}$-outer realization of $G^{i}_{1}$. This is trivial when $i=x-1$;
further, when $i<x-1$, if $e_{i}$ were not incident to the outer face of
$\Gamma^{i}_{1}$, then $e_{x-1}$ could not be incident to the outer face of
$\Gamma_{1}$ without violating the planarity of $\Gamma_{1}$.

Our algorithm works by induction on $i$ in order to either conclude that
$G^{i}_{1}$ admits no $e_{i}$-outer realization (and thus $G_{1}$ admits no
$e_{x-1}$-outer realization), or to determine an $e_{i}$-optimal realization
$\Gamma^{i}_{1}$ of $G^{i}_{1}$. This is trivial when $i=1$, namely
$G^{1}_{1}$ is the $3$-cycle $c_{1}$ which has a unique planar straight-line
realization $\Gamma^{1}_{1}:=\mathcal{C}_{1}$, up to a rigid transformation;
then $\Gamma^{1}_{1}$ is indeed an $e_{1}$-optimal realization.

Assume that we have an $e_{i-1}$-optimal realization $\Gamma^{i-1}_{1}$ of
$G^{i-1}_{1}$, for some $i\in\\{2,\dots,x-1\\}$; indeed, if we already
concluded that $G_{1}$ admits no $e_{x-1}$-outer realization, there is nothing
else to do.

Note that the cycles $c_{i-1}$ and $c_{i}$ share the edge $e_{i-1}$; let
$v_{i-1}$ and $v_{i}$ be the vertices of $c_{i-1}$ and $c_{i}$, respectively,
not incident to $e_{i-1}$. Any straight-line realization of $G^{i}_{1}$ is of
one of two types: it is a different-side realization if $v_{i-1}$ and $v_{i}$
lie on different sides of the line through $e_{i-1}$, while it is a same-side
realization if $v_{i-1}$ and $v_{i}$ lie on the same side of the line through
$e_{i-1}$.

In order to determine whether an $e_{i}$-outer realization of $G^{i}_{1}$
exists, we combine $\Gamma^{i-1}_{1}$ with $\mathcal{C}_{i}$ in two ways, so
to form a different-side realization and a same-side realization. Namely,
$G^{i-1}_{1}$ and $c_{i}$ share the edge $e_{i-1}$; hence, once
$\Gamma^{i-1}_{1}$ and $\mathcal{C}_{i}$ coincide on the representation of
$e_{i-1}$, it still remains to decide whether $v_{i-1}$ and $v_{i}$ lie on
different sides or on the same side of the line through $e_{i-1}$. This choice
leads to two straight-line realizations of $G^{i}_{1}$, which we respectively
denote by $\Gamma^{i,a}_{1}$ and $\Gamma^{i,b}_{1}$.

We check each of $\Gamma^{i,a}_{1}$ and $\Gamma^{i,b}_{1}$ for planarity and
discard each realization that is not planar. Further, if $\Gamma^{i,b}_{1}$
was not discarded, then the triangles $\mathcal{C}_{i-1}$ and
$\mathcal{C}_{i}$ are one nested into the other one (except for the edge
$e_{i-1}$, which is common to both triangles) in such a realization. If
$\mathcal{C}_{i}$ is nested into $\mathcal{C}_{i-1}$, then we discard
$\Gamma^{i,b}_{1}$, as it is not an $e_{i}$-outer realization of $G^{i}_{1}$.
We have now three cases:

  * •

If we did not discard $\Gamma^{i,b}_{1}$, then we set
$\Gamma^{i}_{1}=\Gamma^{i,b}_{1}$. Indeed, if we did not discard
$\Gamma^{i,b}_{1}$, then $\Gamma^{i,b}_{1}$ is a planar straight-line
realization of $G^{i}_{1}$ in which $\mathcal{C}_{i-1}$ is nested into
$\mathcal{C}_{i}$; this implies that all of $\Gamma^{i-1}_{1}$ lies inside
$\mathcal{C}_{i}$, hence $\mathcal{I}_{\Gamma^{i}_{1}}$ coincides with the
closure of the interior of $\mathcal{C}_{i}$. It follows that $\Gamma^{i}_{1}$
is an $e_{i}$-optimal realization of $G^{i}_{1}$, given that in any planar
straight-line realization of $G^{i}_{1}$ the cycle $c_{i}$ is represented by
the triangle $\mathcal{C}_{i}$.

  * •

If we discarded $\Gamma^{i,b}_{1}$ but we did not discard $\Gamma^{i,a}_{1}$,
then we set $\Gamma^{i}_{1}=\Gamma^{i,a}_{1}$. We prove that $\Gamma^{i}_{1}$
is an $e_{i}$-optimal realization of $G^{i}_{1}$.

First, we prove that there exists no same-side $e_{i}$-outer realization of
$G^{i}_{1}$. This is obvious if $\Gamma^{i,b}_{1}$ was discarded because
$\mathcal{C}_{i}$ is nested into $\mathcal{C}_{i-1}$, as the same would be
true in any same-side realization of $G^{i}_{1}$. Suppose hence that
$\Gamma^{i,b}_{1}$ was discarded because it is not planar and suppose, for a
contradiction, that there exists a same-side $e_{i}$-outer realization
$\Psi^{i}_{1}$ of $G^{i}_{1}$. Since $\Gamma^{i-1}_{1}$ is $e_{i-1}$-optimal,
it is $e_{i-1}$-smaller than the restriction of $\Psi^{i}_{1}$ to
$G^{i-1}_{1}$; hence, we can apply Lemma 21 with $H=G^{i-1}_{1}$, $K=c_{i}$,
$\mathcal{G}=\Psi^{i}_{1}$, $e=e_{i-1}$, and
$\mathcal{H}^{\prime}=\Gamma^{i-1}_{1}$, in order to obtain a planar straight-
line realization $\Gamma^{i,*}_{1}$ of $G$ whose restriction to $G^{i-1}_{1}$
is $\Gamma^{i-1}_{1}$. Since $\Psi^{i}_{1}$ is a same-side realization of
$G^{i}_{1}$, we have that $\Gamma^{i,*}_{1}$ is also a same-side realization
of $G^{i}_{1}$. Hence, $\Gamma^{i,*}_{1}$ is the same realization as
$\Gamma^{i,b}_{1}$, a contradiction to the fact that $\Gamma^{i,b}_{1}$ is not
planar.

Second, since we did not discard $\Gamma^{i,a}_{1}$, we have that
$\Gamma^{i}_{1}=\Gamma^{i,a}_{1}$ is planar. This, together with the fact that
$\Gamma^{i}_{1}$ is a different-side realization, implies that
$\Gamma^{i}_{1}$ is an $e_{i}$-outer realization. The proof that
$\Gamma^{i}_{1}$ is an $e_{i}$-optimal realization of $G^{i}_{1}$ easily
follows by induction. Namely, as proved above, any $e_{i}$-outer realization
of $G^{i}_{1}$ is a different-side realization. Consider any such realization
$\Psi^{i}_{1}$ and let $\Psi^{i-1}_{1}$ be the restriction of $\Psi^{i}_{1}$
to the vertices and edges of $G^{i-1}_{1}$. By induction, we have that
$\Gamma^{i-1}_{1}$ is $e_{i-1}$-smaller than $\Psi^{i-1}_{1}$, hence
$\Gamma^{i}_{1}$ is $e_{i}$-smaller than $\Psi^{i}_{1}$, given that the
realization $\mathcal{C}_{i}$ of $c_{i}$ coincides in $\Gamma^{i}_{1}$ and
$\Psi^{i}_{1}$.

  * •

Finally, if we discarded both $\Gamma^{i,a}_{1}$ and $\Gamma^{i,b}_{1}$, we
conclude that there exists no $e_{i}$-outer realization of $G^{i}_{1}$.
Namely, the proof that there exists no same-side $e_{i}$-outer realization of
$G^{i}_{1}$ is the same as for the case in which we discarded
$\Gamma^{i,b}_{1}$ but we did not discard $\Gamma^{i,a}_{1}$. The proof that
there exists no different-side $e_{i}$-outer realization of $G^{i}_{1}$ is
also very similar to the proof for a same-side realization. Indeed, that we
discarded $\Gamma^{i,a}_{1}$ was unequivocally due to the fact that it is not
planar. Suppose, for a contradiction, that there exists a different-side
$e_{i}$-outer realization $\Psi^{i}_{1}$ of $G^{i}_{1}$. Since
$\Gamma^{i-1}_{1}$ is $e_{i-1}$-optimal, it is $e_{i-1}$-smaller than the
restriction of $\Psi^{i}_{1}$ to $G^{i-1}_{1}$; hence, we can apply Lemma 21
with $H=G^{i-1}_{1}$, $K=c_{i}$, $\mathcal{G}=\Psi^{i}_{1}$, $e=e_{i-1}$, and
$\mathcal{H}^{\prime}=\Gamma^{i-1}_{1}$, in order to obtain a planar straight-
line realization $\Gamma^{i,*}_{1}$ of $G$ whose restriction to $G^{i-1}_{1}$
is $\Gamma^{i-1}_{1}$. Since $\Psi^{i}_{1}$ is a different-side realization of
$G^{i}_{1}$, we have that $\Gamma^{i,*}_{1}$ is also a different-side
realization of $G^{i}_{1}$. Hence, $\Gamma^{i,*}_{1}$ is the same realization
as $\Gamma^{i,a}_{1}$, a contradiction to the fact that $\Gamma^{i,a}_{1}$ is
not planar.

It remains to show how the described algorithm can be implemented to run in
$O(n)$ time. Note that a naive implementation of our algorithm would take
$O(n^{2})$ time. Indeed, for each of the $O(n)$ inductive steps, the
realizations $\Gamma^{i,a}_{1}$ and $\Gamma^{i,b}_{1}$, together with their
plane embeddings $\mathcal{E}(\Gamma^{i,a}_{1})$ and
$\mathcal{E}(\Gamma^{i,b}_{1})$, can be constructed in $O(1)$ time from
$\Gamma^{i-1}_{1}$ and its plane embedding $\mathcal{E}(\Gamma^{i-1}_{1})$.
Further, the test on whether $\mathcal{C}_{i}$ is nested into
$\mathcal{C}_{i-1}$ in $\Gamma^{i,b}_{1}$ can also be performed in $O(1)$
time. Finally, by Theorem 3.1, it can be tested in $O(n)$ time whether
$\Gamma^{i,a}_{1}$ and $\Gamma^{i,b}_{1}$ are planar straight-line
realizations of $G^{i-1}_{1}$ respecting $\mathcal{E}(\Gamma^{i,a}_{1})$ and
$\mathcal{E}(\Gamma^{i,b}_{1})$, respectively.

In order to achieve $O(n)$ total running time, we do not test planarity at
each inductive step. Rather, for $i=1,\dots,x-1$, we compute a “candidate”
straight-line realization $\Gamma^{i}_{1}$ of $G^{i}_{1}$, and we only test
for the planarity of the final realization $\Gamma^{x-1}_{1}$. “Candidate”
here means $e_{i}$-optimal, however only in the case in which $\Gamma^{i}_{1}$
is planar. Indeed, $\Gamma^{i}_{1}$ might not be planar, in which case the
candidate straight-line realization $\Gamma^{i}_{1}$ of $G^{i}_{1}$ is not
required to satisfy any specific geometric constraint.

More formally, for $i=1,\dots,x-1$, we construct a straight-line realization
$\Gamma^{i}_{1}$ of $G^{i}_{1}$, together with a plane embedding
$\mathcal{E}(\Gamma^{i}_{1})$, satisfying the following invariant: If an
$e_{i}$-outer realization of $G^{i}_{1}$ exists, then $\Gamma^{i}_{1}$ is an
$e_{i}$-optimal realization of $G^{i}_{1}$ and $\mathcal{E}(\Gamma^{i}_{1})$
is the plane embedding of $G^{i}_{1}$ corresponding to $\Gamma^{i}_{1}$. We
again remark that, if an $e_{i}$-outer realization of $G^{i}_{1}$ does not
exist, then $\Gamma^{i}_{1}$ is non-planar or the edge $e_{i}$ is not incident
to the outer face of $\Gamma^{i}_{1}$.

In order to construct $\Gamma^{i}_{1}$, we maintain:

  * •

the boundary $\mathcal{B}^{i}_{1}$ of the convex hull of $\Gamma^{i}_{1}$
(that is, the sequence of vertices along $\mathcal{B}^{i}_{1}$);

  * •

a Boolean value $\beta(e_{i})$ such that $\beta(e_{i})=\texttt{True}$ if and
only if $e_{i}$ is an edge of $\mathcal{B}^{i}_{1}$; and

  * •

a distinguished vertex $\xi_{i}$ of $\mathcal{B}^{i}_{1}$ (this information is
only available if $\beta(e_{i})=\texttt{False}$; the meaning of $\xi_{i}$ will
be explained later).

Our algorithm only guarantees the correctness of the above information in the
case in which $G^{i}_{1}$ admits an $e_{i}$-outer realization. For example, if
$G^{i}_{1}$ does not admit an $e_{i}$-outer realization, $\mathcal{B}^{i}_{1}$
might not correctly represent the boundary of the convex hull of
$\Gamma^{i}_{1}$.

Before describing our algorithm, we introduce a problem and a known solution
for it. Let $\mathcal{Z}$ be a planar straight-line drawing of a path
$S=(z_{1},z_{2},\dots,z_{m})$ and, for any $i\in\\{1,\dots,m\\}$, let
$\mathcal{Z}_{i}$ be the restriction of $\mathcal{Z}$ to the subpath
$Z_{i}=(z_{1},z_{2},\dots,z_{i})$ of $Z$. Suppose that the locations of
$z_{1},z_{2},\dots,z_{m}$ in $\mathcal{Z}$ are unveiled one at a time, in that
order. For $i=1,\dots,m$, when the location of $z_{i}$ is unveiled, we want to
compute the boundary of the convex hull of $\mathcal{Z}_{i}$. Melkman [37]
presented an algorithm to solve the problem (i.e., to compute the boundaries
of the convex hulls of
$\mathcal{Z}_{1},\mathcal{Z}_{2},\dots,\mathcal{Z}_{m}$) in total $O(m)$ time.

This result allows us to compute the boundaries
$\mathcal{B}^{1}_{1},\mathcal{B}^{2}_{1},\dots,\mathcal{B}^{x-1}_{1}$ of the
convex hulls of $\Gamma^{1}_{1},\Gamma^{2}_{1},\dots,\Gamma^{x-1}_{1}$ in
total $O(n)$ time. Indeed, an easy inductive argument proves that
$G^{x-1}_{1}$ contains a path $Z$ spanning all its vertices and such that, for
$i=1,\dots,x-1$, the vertices of $G^{i}_{1}$ induce a subpath $Z_{i}$ of $Z$.
For $i=2,\dots,x-1$, our algorithm constructs $\Gamma^{i}_{1}$ from
$\Gamma^{i-1}_{1}$ by assigning a position to the vertex $v_{i}$ of
$\mathcal{C}_{i}$ not incident to $e_{i-1}$; once we have done that, the
algorithm by Melkman [37] can be employed in order to compute
$\mathcal{B}^{i}_{1}$ from $\mathcal{B}^{i-1}_{1}$ (more precisely, we run
Melkman’s algorithm [37] in parallel with our algorithm and feed it the
locations of the vertices of $Z$ in the order our algorithm computes them).
Note that, if $G^{i}_{1}$ admits an $e_{i}$-outer realization, then
$\mathcal{B}^{i}_{1}$ is correctly computed, otherwise $\mathcal{B}^{i}_{1}$
might not correctly represent the boundary of the convex hull of
$\Gamma^{i}_{1}$. We will only sketch what Melkman’s algorithm [37] does in
order to compute
$\mathcal{B}^{1}_{1},\mathcal{B}^{2}_{1},\dots,\mathcal{B}^{x-1}_{1}$.

The base case takes $O(1)$ time, as $G^{1}_{1}$ has a unique (planar)
straight-line realization $\Gamma^{1}_{1}=\mathcal{C}_{1}$, up to a rigid
transformation; further, $\mathcal{E}(\Gamma^{1}_{1})$ is easily computed from
$\Gamma^{1}_{1}$, and we have $\mathcal{B}^{1}_{1}=\mathcal{C}_{1}$,
$\beta(e_{1})=\texttt{True}$, and $\xi_{1}=\texttt{Null}$. Now assume that,
for some $i\in\\{2,\dots,x-1\\}$, we have a candidate straight-line
realization $\Gamma^{i-1}_{1}$ of $G^{i-1}_{1}$, together with a plane
embedding $\mathcal{E}(\Gamma^{i-1}_{1})$, satisfying the invariant, the
boundary $\mathcal{B}^{i-1}_{1}$ of the convex hull of $\Gamma^{i-1}_{1}$, the
Boolean value $\beta(e_{i-1})$, and the vertex $\xi_{i-1}$. We are going to
distinguish some cases; common to all the cases is the observation that, if
$\Gamma^{i-1}_{1}$ is not planar, then it is not important how our algorithm
computes $\Gamma^{i}_{1}$, $\mathcal{E}(\Gamma^{i}_{1})$,
$\mathcal{B}^{i}_{1}$, $\beta(e_{i})$, and $\xi_{i}$, because, by the
invariant, $G^{i-1}_{1}$ admits no $e_{i-1}$-outer realization and hence
$G^{i}_{1}$ admits no $e_{i}$-outer realization.

Case 1: $\beta(e_{i-1})=\texttt{True}$. We check whether $\Gamma^{i-1}_{1}$
and $\mathcal{C}_{i}$ can be combined in order to form a same-side
$e_{i}$-outer realization of $G^{i}_{1}$ (assuming that $\Gamma^{i-1}_{1}$ is
planar). Since we know $\mathcal{B}^{i-1}_{1}$, this check only requires
$O(1)$ time. Indeed, once $\mathcal{C}_{i}$ is embedded in such a way that
$v_{i-1}$ and $v_{i}$ lie on the same side of the line through $e_{i-1}$, it
suffices to compare the slopes of the edges of $\mathcal{C}_{i}$ different
from $e_{i-1}$ with the slopes of the segments of $\mathcal{B}^{i-1}_{1}$
incident to the end-vertices of $e_{i-1}$ and different from $e_{i-1}$; see
Fig. 28(a).

  * •

Case 1.1: If the check is successful, we let $\Gamma^{i}_{1}$ be the resulting
straight-line realization of $G^{i}_{1}$; further, the plane embedding
$\mathcal{E}(\Gamma^{i}_{1})$ can be computed in $O(1)$ time from
$\mathcal{E}(\Gamma^{i-1}_{1})$ by inserting the edges of $c_{i}$ incident to
$v_{i}$ next to $e_{i-1}$ in the cyclic order of the edges incident to the
end-vertices of $e_{i-1}$ and by letting the outer face of
$\mathcal{E}(\Gamma^{i}_{1})$ be bounded by the cycle $c_{i}$. Finally, we let
$\mathcal{B}^{i}_{1}=\mathcal{C}_{i}$, $\beta(e_{i})=\texttt{True}$, and
$\xi_{i}=\texttt{Null}$. Note that, if $\Gamma^{i-1}_{1}$ is planar, then
$\Gamma^{i}_{1}$ is an $e_{i}$-optimal realization of $G^{i}_{1}$ (this is the
realization which was earlier called $\Gamma^{i,b}_{1}$).

  * •

Case 1.2: If the check is unsuccessful, we let $\Gamma^{i}_{1}$ be the
straight-line realization obtained from $\Gamma^{i-1}_{1}$ by embedding
$\mathcal{C}_{i}$ in such a way that $v_{i-1}$ and $v_{i}$ lie on different
sides of the line through $e_{i-1}$. Thus, $\Gamma^{i}_{1}$ can be constructed
in $O(1)$ time from $\Gamma^{i-1}_{1}$. The plane embedding
$\mathcal{E}(\Gamma^{i}_{1})$ can also be computed in $O(1)$ time from
$\mathcal{E}(\Gamma^{i-1}_{1})$; indeed, the set of clockwise orders of the
edges incident to each vertex in $\mathcal{E}(\Gamma^{i}_{1})$ is computed as
in Case 1.1, while the boundary of the outer face of
$\mathcal{E}(\Gamma^{i}_{1})$ is computed from the one of
$\mathcal{E}(\Gamma^{i-1}_{1})$ by letting the two edges of $c_{i}$ incident
to $v_{i}$ replace the edge $e_{i-1}$. Note that, if $\Gamma^{i-1}_{1}$ is
planar, then $\Gamma^{i}_{1}$ is an $e_{i}$-optimal realization of
$G^{i}_{1}$; this is the realization which was earlier called
$\Gamma^{i,a}_{1}$.

(a) (b) (c) (d) (e)

Figure 28: Embedding $\mathcal{C}_{i}$ (thick black) together with
$\Gamma^{i-1}_{1}$. (a) In order to establish whether $\Gamma^{i-1}_{1}$
(whose convex hull is gray) fits inside $\mathcal{C}_{i}$, the slopes of the
edges of $\mathcal{C}_{i}$ incident to $v_{i}$ are compared with the slopes of
the segments of $\mathcal{B}^{i-1}_{1}$ incident to the end-vertices of
$e_{i-1}$ and different from $e_{i-1}$ (lines through these segments are dark
gray). (b) If $\mathcal{C}_{i}$ is embedded so that $v_{i-1}$ and $v_{i}$ lie
on different sides of the line through $e_{i-1}$, then $\mathcal{B}^{i}_{1}$
has to be computed; Melkman’s algorithm [37] examines the segments from
$v_{i}$ to the vertices that follow $s_{i-1}$ in counter-clockwise order along
$\mathcal{B}^{i-1}_{1}$, until it finds a segment (dark gray) from $v_{i}$ to
a vertex $s^{\prime}_{i-1}$ that keeps the previously encountered segment
$\sigma$ to the right. (c) If $e_{i}$ lies in the interior of the convex hull
of $\Gamma^{i}_{1}$, except possibly for its end-vertices, then the segments
$\sigma$ and $\tau$ of $\mathcal{B}^{i}_{1}$ incident to $\xi_{i}=v_{i}$
represent the only “way out” of $\mathcal{B}^{i}_{1}$ for a planar straight-
line realization of $G^{x-1}_{1}$; in particular, in any $e_{x-1}$-outer
realization of $G^{x-1}_{1}$, the vertices and edges that are not in
$G^{i}_{1}$ and that lie inside $\mathcal{B}^{i}_{1}$ can only lie in the dark
gray regions incident to $\sigma$ and $\tau$. (d) Illustration for the case in
which $v_{i}$ lies outside the convex hull of $\Gamma^{i-1}_{1}$ and
$\xi_{i-1}$ is the end-vertex of $e_{i}$ different from $v_{i}$. (e)
Illustration for the case in which $v_{i}$ lies outside the convex hull of
$\Gamma^{i-1}_{1}$ and $\xi_{i-1}$ is not the end-vertex of $e_{i}$ different
from $v_{i}$.

In order to compute $\mathcal{B}^{i}_{1}$ from $\mathcal{B}^{i-1}_{1}$,
Melkman’s algorithm [37] works as follows; refer to Fig. 28(b). Let $s_{i-1}$
and $t_{i-1}$ be the end-vertices of $e_{i-1}$ and assume that $s_{i-1}$
immediately precedes $t_{i-1}$ in clockwise order along
$\mathcal{B}^{i-1}_{1}$. Since $v_{i}$ is a vertex of $\mathcal{B}^{i}_{1}$,
the algorithm needs to find the vertices of $\mathcal{B}^{i-1}_{1}$ that
follow $v_{i}$ in clockwise and counter-clockwise order along
$\mathcal{B}^{i}_{1}$. In order to find the vertex that follows $v_{i}$ in
counter-clockwise order along $\mathcal{B}^{i}_{1}$ (the computation of the
other vertex is done similarly), the algorithm computes the segments from
$v_{i}$ to the vertices of $\mathcal{B}^{i-1}_{1}$, starting from $s_{i-1}$
and proceeding in counter-clockwise order along $\mathcal{B}^{i-1}_{1}$. This
computation stops when a segment from $v_{i}$ to a vertex $s^{\prime}_{i-1}$
of $\mathcal{B}^{i-1}_{1}$ is considered such that the oriented line that
passes first through $v_{i}$ and then through $s^{\prime}_{i-1}$ keeps the
previously encountered segment $\sigma$ to the right. When that happens, the
end-vertex of $\sigma$ different from $v_{i}$ is the vertex that follows
$v_{i}$ in counter-clockwise order along $\mathcal{B}^{i}_{1}$. This
computation does not, in general, take $O(1)$ time, however it takes linear
time in the number of vertices of $\mathcal{B}^{i-1}_{1}$ that are not in
$\mathcal{B}^{i}_{1}$, hence it takes $O(n)$ time over all the convex hull
computations.

Let $\sigma$ and $\tau$ be the segments of $\mathcal{B}^{i}_{1}$ incident to
$v_{i}$. In order to compute $\beta(e_{i})$ and $\xi_{i}$, we check whether
$e_{i}$ coincides with one of $\sigma$ and $\tau$. In the positive case, we
let $\beta(e_{i})=\texttt{True}$ and $\xi_{i}=\texttt{Null}$. In the negative
case, we let $\beta(e_{i})=\texttt{False}$ and $\xi_{i}=v_{i}$. We are now
ready to explain the meaning of the information conveyed in $\xi_{i}$; refer
to Fig. 28(c). If $e_{i}$ lies in the interior of the convex hull of
$\Gamma^{i}_{1}$, except possibly for one of its end-vertices, then the
segments $\sigma$ and $\tau$ of $\mathcal{B}^{i}_{1}$ incident to $\xi_{i}$
represent the only “way out” of $\mathcal{B}^{i}_{1}$ for a planar straight-
line realization of $G^{x-1}_{1}$. Formally, let $j$ be the smallest index
such that $j>i$ and such that $v_{j}$ lies outside $\mathcal{B}^{i}_{1}$ in a
planar straight-line realization of $G^{j}_{1}$, if any such an index exists;
then (at least) one of the two edges incident to $v_{j}$ in $G^{j}_{1}$
crosses $\sigma$ or $\tau$. This very same property is exploited in Melkman’s
algorithm [37], and comes from the fact that, by the connectivity of
$G^{i}_{1}$, any path that starts at $v_{i}$, that does not share any vertex
with $G^{i}_{1}$ other than $v_{i}$, and that first intersects the interior of
the convex hull of $\Gamma^{i}_{1}$ and then crosses $\mathcal{B}^{i}_{1}$ in
a segment different from $\sigma$ and $\tau$ crosses $\Gamma^{i}_{1}$ as well.

Case 2: $\beta(e_{i-1})=\texttt{False}$. In this case $\Gamma^{i-1}_{1}$ lies
on both sides of the line through $e_{i-1}$, hence $\Gamma^{i-1}_{1}$ and
$\mathcal{C}_{i}$ cannot be combined in order to form a same-side
$e_{i}$-outer realization of $G^{i}_{1}$, even if $\Gamma^{i-1}_{1}$ is
planar. Thus, as in Case 1.2, we let $\Gamma^{i}_{1}$ be the straight-line
realization obtained from $\Gamma^{i-1}_{1}$ by embedding $\mathcal{C}_{i}$ in
such a way that $v_{i-1}$ and $v_{i}$ lie on different sides of the line
through $e_{i-1}$; this is again the realization which was earlier called
$\Gamma^{i,a}_{1}$. The plane embedding $\mathcal{E}(\Gamma^{i}_{1})$ is
computed in $O(1)$ time from $\mathcal{E}(\Gamma^{i-1}_{1})$ as in Case 1.2.
Then $\Gamma^{i}_{1}$ satisfies the invariant; indeed, in the description of
the algorithm, it was proved that, if $\Gamma^{i,a}_{1}$ is planar, then it is
$e_{i}$-optimal, otherwise $G^{i}_{1}$ admits no $e_{i}$-outer realization.
Further, $\Gamma^{i}_{1}$ can be constructed in $O(1)$ time from
$\Gamma^{i-1}_{1}$. Note that, in this case, it might happen that
$\Gamma^{i}_{1}$ is not planar even if $\Gamma^{i-1}_{1}$ is planar; however,
we do not check the planarity of $\Gamma^{i}_{1}$ at this time.

In order to compute $\mathcal{B}^{i}_{1}$, $\beta(e_{i})$, and $\xi_{i}$, we
exploit the information stored in $\xi_{i-1}$. As explained in Case 1.2, if
$\Gamma^{i-1}_{1}$ is planar, the value $\xi_{i-1}$ represents a vertex on the
boundary $\mathcal{B}^{i-1}_{1}$ of the convex hull of $\Gamma^{i-1}_{1}$ such
that $v_{i}$ lies outside $\mathcal{B}^{i-1}_{1}$ only if the (at least one)
edge $e$ of $c_{i}$ incident to $v_{i}$ and not incident to $\xi_{i-1}$
crosses $\sigma$ or $\tau$, where $\sigma$ and $\tau$ are the segments
incident to $\xi_{i-1}$ in $\mathcal{B}^{i-1}_{1}$. Hence, we (as in Melkman’s
algorithm [37]) check in $O(1)$ time whether $e$ crosses $\sigma$ or $\tau$.

  * •

In the positive case, $v_{i}$ lies outside the convex hull of
$\Gamma^{i-1}_{1}$; then $\mathcal{B}^{i}_{1}$ is constructed as in Case 1.2,
where the segment between $\sigma$ and $\tau$ that crosses $e$ plays the role
of $e_{i-1}$. If $\xi_{i-1}$ is the end-vertex of $e_{i}$ different from
$v_{i}$, as in Fig. 28(d), then we set $\beta(e_{i})=\texttt{True}$ and
$\xi_{i}=\texttt{Null}$ (in this case $G^{i}_{1}$ “made it out” of
$\mathcal{B}^{i-1}_{1}$), otherwise, as in Fig. 28(e), we set
$\beta(e_{i})=\texttt{False}$ and $\xi_{i}=v_{i}$.

  * •

In the negative case, $v_{i}$ lies inside the convex hull of
$\Gamma^{i-1}_{1}$ or $\Gamma^{i}_{1}$ is not planar (or both). Hence, we set
$\mathcal{B}^{i}_{1}=\mathcal{B}^{i-1}_{1}$, $\beta(e_{i})=\texttt{False}$,
and $\xi_{i}=\xi_{i-1}$.

This concludes the description of the inductive case of our algorithm. Each
inductive step takes $O(1)$ time, except for the computation of the boundaries
$\mathcal{B}^{1}_{1},\mathcal{B}^{2}_{1},\dots,\mathcal{B}^{x-1}_{1}$, which
however takes total $O(n)$ time as explained above. Hence, the overall running
time of the algorithm is in $O(n)$. ∎

Figure 29: The outerplane embedding of an outerpillar. The gray face is the
one bounded by $c_{x}$. The graphs $G_{1}$ and $G_{2}$ are enclosed inside fat
curves.

Proof of Theorem 6.2. The proof uses several ideas from the proof of Theorem
6.1. We hence omit details of arguments that have been already detailed in
that proof.

Let $G=(V,E,\lambda)$ be an $n$-vertex weighted maximal outerpillar (as the
one in Fig. 29) and let $\mathcal{O}$ be its outerplane embedding, which can
be found in $O(n)$ time [21, 38, 50]. Since $G$ is an outerpillar, its dual
tree is a caterpillar $T$, whose spine we denote by $P:=(p_{1},\dots,p_{k})$;
note that $T$ can be easily recovered from $\mathcal{O}$ in $O(n)$ time. We
arbitrarily select two leaves of $T$, respectively adjacent to $p_{1}$ and
$p_{k}$, and denote them by $p_{0}$ and $p_{k+1}$; we further denote by
$\overline{P}$ the path $(p_{0},p_{1},\dots,p_{k},p_{k+1})$. Each node $p_{i}$
of $\overline{P}$ corresponds to an internal face of $\mathcal{O}$; we denote
by $c_{i}$ the $3$-cycle of $G$ bounding such a face. Further, each node
$p_{i}$ in $\overline{P}$ is adjacent to at most one leaf not in
$\overline{P}$ (the satisfaction of this property was the reason to augment
$P$ to $\overline{P}$), which corresponds to an internal face of
$\mathcal{O}$; we denote by $d_{i}$ the $3$-cycle of $G$ bounding such a face.
Each cycle $c_{i}$ has a unique (planar) straight-line realization (up to a
rigid transformation), which we denote by $\mathcal{C}_{i}$, and each cycle
$d_{i}$ has a unique (planar) straight-line realization (up to a rigid
transformation), which we denote by $\mathcal{D}_{i}$. For $i=0,\dots,k$, let
$e_{i}$ be the edge of $G$ that is dual to the edge $(p_{i},p_{i+1})$ of
$\overline{P}$; note that $e_{i}$ is an internal edge of $\mathcal{O}$.
Further, for every index $i\in\\{1,\dots,k\\}$ such that $d_{i}$ exists, let
$g_{i}$ be the edge shared by $c_{i}$ and $d_{i}$.

Let $c^{*}$ be a $3$-cycle of $G$ whose edges have a sum of the lengths which
is maximum among all the $3$-cycles of $G$. Let $x\in\\{0,1,\dots,k+1\\}$ be
the index such that we have either $c^{*}=c_{x}$ or $c^{*}=d_{x}$. Let $G_{1}$
be the subgraph of $G$ composed of the $3$-cycles $c_{i}$ and of the
$3$-cycles $d_{i}$ with $i=0,\dots,x-1$ (some of the $3$-cycles $d_{i}$ might
not exist). Analogously, let $G_{2}$ be the subgraph of $G$ composed of the
$3$-cycles $c_{i}$ and of the $3$-cycles $d_{i}$ with $i=x+1,\dots,k+1$
(again, some of the $3$-cycles $d_{i}$ might not exist). One of these graphs
might be undefined if $x=0$ or $x=k+1$; however, in the following, we assume
that $1\leq x\leq k$ as the arguments for the cases $x=0$ and $x=k+1$ are
analogous and actually simpler. Note that $G_{1}$ and $G_{2}$ are maximal
outerpillars. Also, we assume that the $3$-cycle $d_{x}$ exists, as the
argument for the case in which it does not is simpler.

Assume that a planar straight-line realization $\Gamma$ of $G$ exists; for
$i=1,2$, let $\Gamma_{i}$ be the restriction of $\Gamma$ to $G_{i}$. If
$c^{*}=c_{x}$, then $c_{x}$ does not lie inside any $3$-cycle of $G$ in
$\Gamma$. If $c^{*}=d_{x}$, then $c_{x}$ might lie inside $d_{x}$ in $\Gamma$,
however it does not lie inside any other $3$-cycle of $G$ in $\Gamma$, as
otherwise, by planarity, such a $3$-cycle would also contain $d_{x}$, which is
not possible. Therefore, both if $c^{*}=c_{x}$ and if $c^{*}=d_{x}$, we have
that $\Gamma_{1}$ is an $e_{x-1}$-outer realization of $G_{1}$ and that
$\Gamma_{2}$ is an $e_{x}$-outer realization of $G_{2}$.

We show an $O(n^{3})$-time algorithm that either concludes that $G_{1}$ admits
no $e_{x-1}$-outer realization or constructs an $e_{x-1}$-optimal set
$\mathcal{R}_{1}$ of $e_{x-1}$-outer realizations of $G_{1}$, where for each
realization $\Gamma_{1}$ in $\mathcal{R}_{1}$ the plane embedding
$\mathcal{E}(\Gamma_{1})$ is constructed as well. The same algorithm is then
also used in order to either conclude that $G_{2}$ admits no $e_{x}$-outer
realization or to construct an $e_{x}$-optimal set $\mathcal{R}_{2}$ of
$e_{x}$-outer realizations of $G_{2}$, where for each realization $\Gamma_{2}$
in $\mathcal{R}_{2}$ the plane embedding $\mathcal{E}(\Gamma_{2})$ is
constructed as well.

For $i=0,1,\dots,x-1$, let $G^{i}_{1}$ be the subgraph of $G_{1}$ composed of
the $3$-cycles $c_{0},c_{1},\dots,c_{i}$ and of the $3$-cycles
$d_{0},d_{1},\dots,d_{i}$ (some of these $3$-cycles might not exist); note
that $G^{x-1}_{1}=G_{1}$. As in the proof of Theorem 6.1, we use the
observation that the restriction of any $e_{x-1}$-outer realization of $G_{1}$
to $G^{i}_{1}$ is an $e_{i}$-outer realization of $G^{i}_{1}$.

Our algorithm works by induction on $i$ in order to either conclude that
$G^{i}_{1}$ admits no $e_{i}$-outer realization (and thus $G_{1}$ admits no
$e_{x-1}$-outer realization), or to determine an $e_{i}$-optimal set
$\mathcal{R}^{i}_{1}$ of $e_{i}$-outer realizations of $G^{i}_{1}$ with
$|\mathcal{R}^{i}_{1}|\leq i+1$, where for each realization $\Gamma^{i}_{1}$
in $\mathcal{R}^{i}_{1}$ the plane $\mathcal{E}(\Gamma^{i}_{1})$ is
constructed as well. This is trivial when $i=0$, namely $G^{0}_{1}$ is the
$3$-cycle $c_{0}$ which has a unique planar straight-line realization
$\Gamma^{0}_{1}:=\mathcal{C}_{0}$, up to a rigid transformation; then
$\mathcal{R}^{0}_{1}:=\\{\Gamma^{0}_{1}\\}$ is indeed an $e_{0}$-optimal set
of $e_{0}$-outer realizations of $G^{0}_{1}$ with $|\mathcal{R}^{0}_{1}|\leq
1$ and $\mathcal{E}(\Gamma^{0}_{1})$ is easily computed from $\Gamma^{0}_{1}$.

Assume that we have an $e_{i-1}$-optimal set $\mathcal{R}^{i-1}_{1}$ of
$e_{i-1}$-outer realizations of $G^{i-1}_{1}$ with
$|\mathcal{R}^{i-1}_{1}|\leq i$, for some $i\in\\{1,\dots,x-1\\}$, and we
have, for each realization $\Gamma^{i-1}_{1}$ in $\mathcal{R}^{i-1}_{1}$, the
plane embedding $\mathcal{E}(\Gamma^{i-1}_{1})$; indeed, if we already
concluded that $G_{1}$ admits no $e_{x-1}$-outer realization, there is nothing
else to do. We present an algorithm that either concludes that $G_{1}$ admits
no $e_{x-1}$-outer realization or constructs the set $\mathcal{R}^{i}_{1}$
and, for each realization $\Gamma^{i}_{1}$ in $\mathcal{R}^{i}_{1}$, the plane
embedding $\mathcal{E}(\Gamma^{i}_{1})$. The algorithm consists of three
steps.

  * •

Step 1. In the first step, we aim for the construction of an $e_{i}$-outer
realization of $G^{i}_{1}$ in which both $G^{i-1}_{1}$ and $d_{i}$ lie inside
$c_{i}$ (except for the edges $e_{i-1}$ and $g_{i}$, which $c_{i}$ shares with
$G^{i-1}_{1}$ and $d_{i}$, respectively), as the one in Fig. 30(a). This is
done by checking whether any of the $O(n)$ realizations of $G^{i-1}_{1}$ in
$\mathcal{R}^{i-1}_{1}$ fits inside $\mathcal{C}_{i}$ together with
$\mathcal{D}_{i}$. More precisely, we act as follows.

    1. (A)

We test in $O(1)$ time whether $\mathcal{C}_{i-1}$ lies inside
$\mathcal{C}_{i}$ once they coincide on the representation of $e_{i-1}$ and
once their vertices not incident to $e_{i-1}$ lie on the same side of the line
through $e_{i-1}$. If the test is positive, we proceed with the first step of
the algorithm, otherwise we conclude that no realization of $G^{i-1}_{1}$ fits
inside $\mathcal{C}_{i}$, we terminate the first step of the algorithm and
proceed to the second one.

    2. (B)

We test in $O(1)$ time whether $\mathcal{D}_{i}$ lies inside $\mathcal{C}_{i}$
once they coincide on the representation of $g_{i}$ and once their vertices
not incident to $g_{i}$ lie on the same side of the line through $g_{i}$; if
$d_{i}$ does not exist, this test is skipped. If the test is positive, we
proceed with the first step of the algorithm, otherwise we conclude that
$\mathcal{D}_{i}$ does not fit inside $\mathcal{C}_{i}$, we terminate the
first step of the algorithm and proceed to the second one.

    3. (C)

For each realization $\Gamma^{i-1}_{1}$ of $G^{i-1}_{1}$ in
$\mathcal{R}^{i-1}_{1}$, we construct a straight-line realization
$\Gamma^{i}_{1}$ of $G^{i}_{1}$ in which $G^{i-1}_{1}$ is represented by
$\Gamma^{i-1}_{1}$ and $\mathcal{C}_{i-1}$ and $\mathcal{D}_{i}$ are embedded
inside $\mathcal{C}_{i}$. Such a realization can be obtained in $O(1)$ time by
augmenting $\Gamma^{i-1}_{1}$ with a representation of the edges of $c_{i}$
and $d_{i}$ not in $G^{i-1}_{1}$. Further, the plane embedding
$\mathcal{E}(\Gamma^{i}_{1})$ can be constructed in $O(1)$ time by inserting
the edges incident to $v_{i}$ next to $e_{i-1}$ in the cyclic order of the
edges incident to the end-vertices of $e_{i-1}$, by then inserting the edges
of $d_{i}$ different from $g_{i}$ next to $g_{i}$ in the cyclic order of the
edges incident to the end-vertices of $g_{i}$, and by letting the outer face
of $\mathcal{E}(\Gamma^{i}_{1})$ be bounded by the cycle $c_{i}$. We then test
in $O(n)$ time, by means of Theorem 3.1, whether $\Gamma^{i}_{1}$ is a planar
straight-line realization of $G^{i}_{1}$ respecting
$\mathcal{E}(\Gamma^{i}_{1})$.

(a) (b) (c)

Figure 30: Three $e_{i}$-outer realizations of $G^{i}_{1}$. The cycle $c_{i}$
is represented by a thick line. (a) $G^{i-1}_{1}$ and $d_{i}$ lie inside
$c_{i}$; (b) $G^{i-1}_{1}$ lies inside $c_{i}$ and $d_{i}$ lies outside
$c_{i}$; (c) $G^{i-1}_{1}$ lies outside $c_{i}$.

The total running time of the first step of the algorithm is hence in
$O(n^{2})$. If (at least) one of these tests succeeds in constructing a
realization $\Gamma^{i}_{1}$, then we complete the induction with
$\mathcal{R}^{i}_{1}=\\{\Gamma^{i}_{1}\\}$. If none of the tests succeeds, we
proceed to the second step of the algorithm.

  * •

Step 2. In the second step, we aim for the construction of an $e_{i}$-outer
realization of $G^{i}_{1}$ in which $G^{i-1}_{1}$ lies inside $c_{i}$ (except
for the edge $e_{i-1}$, which is shared by $G^{i-1}_{1}$ and $c_{i}$) and
$d_{i}$ lies outside $c_{i}$ (except for the edge $g_{i}$, which is shared by
$c_{i}$ and $d_{i}$), as in Fig. 30(b). If $d_{i}$ does not exist, then this
step is actually ignored, given that the desired representation of $G^{i}_{1}$
would have been already constructed in the first step. As in the first step,
we first check whether $\mathcal{C}_{i-1}$ lies inside $\mathcal{C}_{i}$ once
they coincide on the representation of $e_{i-1}$ and once their vertices not
incident to $e_{i-1}$ lie on the same side of the line through $e_{i-1}$. If
the test is negative, we conclude that no realization of $G^{i-1}_{1}$ fits
inside $\mathcal{C}_{i}$, we terminate the second step of the algorithm and
proceed to the third one with $\mathcal{R}^{i}_{1}=\emptyset$. If the test is
positive, we independently consider each of the $O(n)$ realizations of
$G^{i-1}_{1}$ in $\mathcal{R}^{i-1}_{1}$, say $\Gamma^{i-1}_{1}$. We augment
$\Gamma^{i-1}_{1}$ to a realization $\Gamma^{i}_{1}$ of $G^{i}_{1}$ (and
compute the plane embedding $\mathcal{E}(\Gamma^{i}_{1})$ from the plane
embedding $\mathcal{E}(\Gamma^{i-1}_{1})$) in $O(1)$ time similarly as in the
first step, except that $\mathcal{D}_{i}$ is now embedded outside
$\mathcal{C}_{i}$ and hence the outer face of $\mathcal{E}(\Gamma^{i}_{1})$ is
now delimited by the edges of $c_{i}$ and $d_{i}$ different from $g_{i}$. By
means of Theorem 3.1, we test in $O(n)$ time whether $\Gamma^{i}_{1}$ is a
planar straight-line realization of $G^{i}_{1}$ respecting
$\mathcal{E}(\Gamma^{i}_{1})$. Hence, the total running time of the second
step is in $O(n^{2})$. If (at least) one of these tests shows that a
realization $\Gamma^{i}_{1}$ of $G^{i}_{1}$ is planar, we conclude this step
by initializing $\mathcal{R}^{i}_{1}=\\{\Gamma^{i}_{1}\\}$. If none of the
tests succeeds, then we initialize $\mathcal{R}^{i}_{1}=\emptyset$. In both
cases, we proceed to the third step of the algorithm.

  * •

Step 3. In the third step, we aim for the construction of (possibly multiple)
$e_{i}$-outer realizations of $G^{i}_{1}$ in which $G^{i-1}_{1}$ lies outside
$c_{i}$ (except for the edge $e_{i-1}$, which is shared by $G^{i-1}_{1}$ and
$c_{i}$), as in Fig. 30(c). This is done as follows. Preliminarly, we
construct a realization of $c_{i}\cup d_{i}$ (if $d_{i}$ exists). In order to
do that, we check in $O(1)$ time whether $\mathcal{D}_{i}$ fits inside
$\mathcal{C}_{i}$; in the positive case, we place it inside $\mathcal{C}_{i}$,
otherwise we place it outside $\mathcal{C}_{i}$. We now independently consider
each $e_{i-1}$-outer realization $\Gamma^{i-1}_{1}$ of $G^{i-1}_{1}$ in
$\mathcal{R}^{i-1}_{1}$ and we put it together with the constructed
representation of $c_{i}\cup d_{i}$ (if $d_{i}$ does not exist, we just put
$\Gamma^{i-1}_{1}$ together with $\mathcal{C}_{i}$), so that the vertices of
$c_{i-1}$ and $c_{i}$ not incident to $e_{i-1}$ lie on different sides of the
line through $e_{i-1}$. This can be done in $O(1)$ time, as in the first and
second steps, by augmenting $\Gamma^{i-1}_{1}$ with a representation of the
edges of $c_{i}$ and $d_{i}$ not in $G^{i-1}_{1}$. The plane embedding of the
constructed representation of $G^{i}_{1}$ can also be constructed in $O(1)$
time from the plane embedding $\mathcal{E}(\Gamma^{i-1}_{1})$, similarly as in
the first and second steps. We now check in $O(n)$ time whether the
constructed representation of $G^{i}_{1}$ is a planar straight-line
realization of $G^{i}_{1}$ respecting the constructed plane embedding, by
means of Theorem 3.1; in the positive case, we add it to
$\mathcal{R}^{i}_{1}$. Hence, the total running time of the third step is in
$O(n^{2})$. After the third step, if $\mathcal{R}^{i}_{1}=\emptyset$, we
conclude that $G_{1}$ admits no $e_{x-1}$-outer realization.

This concludes the description of the algorithm. We now prove its correctness.

First, we prove that $|\mathcal{R}^{i}_{1}|\leq i+1$. This is obvious if the
first step succeeded in the construction of a realization of $G^{i}_{1}$, as
in that case we have $|\mathcal{R}^{i}_{1}|=1<i+1$. Otherwise, at most one
realization of $G^{i}_{1}$ was added to $\mathcal{R}^{i}_{1}$ in the second
step; further, during the third step, at most one realization of $G^{i}_{1}$
was added to $\mathcal{R}^{i}_{1}$ for each realization in
$\mathcal{R}^{i-1}_{1}$. Since $|\mathcal{R}^{i-1}_{1}|\leq i$, by the
inductive hypothesis, it follows that $|\mathcal{R}^{i}_{1}|\leq i+1$.

Second, we have that each realization in $\mathcal{R}^{i}_{1}$ is planar, as
ensured by a test performed on it before the insertion into
$\mathcal{R}^{i}_{1}$. Further, each realization in $\mathcal{R}^{i}_{1}$ is
$e_{i}$-outer. Namely, if the vertices of $c_{i-1}$ and $c_{i}$ that are not
incident to $e_{i-1}$ lie on the same side of the line through $e_{i-1}$, we
test whether $\mathcal{C}_{i-1}$ lies inside $\mathcal{C}_{i}$; further, if
the vertices of $d_{i}$ and $c_{i}$ that are not incident to $g_{i}$ lie on
the same side of the line through $g_{i}$, we test whether $\mathcal{D}_{i}$
lies inside $\mathcal{C}_{i}$. A realization is added to $\mathcal{R}^{i}_{1}$
only if both tests succeed, which ensures that $\mathcal{C}_{i}$ does not lie
inside $\mathcal{C}_{i-1}$ or $\mathcal{D}_{i}$ in any realization in
$\mathcal{R}^{i}_{1}$. A containment of $\mathcal{C}_{i}$ inside any other
$3$-cycle of $G^{i}_{1}$ would contradict the planarity of the corresponding
realization.

Finally, we prove that $\mathcal{R}^{i}_{1}$ is $e_{i}$-optimal. This can be
done very similarly as in the proof of Theorem 6.1. Namely, consider any
$e_{i}$-outer realization $\Psi^{i}_{1}$ of $G^{i}_{1}$ and let
$\Psi^{i-1}_{1}$ be the restriction of $\Psi^{i}_{1}$ to $G^{i-1}_{1}$. Since
$\mathcal{R}^{i-1}_{1}$ is $e_{i-1}$-optimal, there exists an $e_{i-1}$-outer
realization $\Lambda^{i-1}_{1}$ of $G^{i-1}_{1}$ in $\mathcal{R}^{i-1}_{1}$
such that $\Lambda^{i-1}_{1}$ is $e_{i-1}$-smaller than $\Psi^{i-1}_{1}$.
Hence, we can apply Lemma 21 with $H=G^{i-1}_{1}$, $K=c_{i}\cup d_{i}$ (or
$K=c_{i}$ if $d_{i}$ does not exist), $\mathcal{G}=\Psi^{i}_{1}$, $e=e_{i-1}$,
and $\mathcal{H}^{\prime}=\Lambda^{i-1}_{1}$, in order to obtain an
$e_{i}$-outer realization $\Lambda^{i}_{1}$ of $G^{i}_{1}$ whose restriction
to $G^{i-1}_{1}$ can be obtained by a rigid transformation of
$\Lambda^{i-1}_{1}$ and such that $\mathcal{C}_{i-1}$ lies inside
$\mathcal{C}_{i}$ in $\Lambda^{i}_{1}$ if and only if $\mathcal{C}_{i-1}$ lies
inside $\mathcal{C}_{i}$ in $\Psi^{i}_{1}$. It only remains to prove that
$\Lambda^{i}_{1}$, or an $e_{i}$-outer realization that is $e_{i}$-smaller
than $\Lambda^{i}_{1}$, actually belongs to $\mathcal{R}^{i}_{1}$.

First, if $\mathcal{R}^{i}_{1}$ contains a single realization $\Gamma^{i}_{1}$
added during the first step, then the outer face of $\Gamma^{i}_{1}$ is
bounded by $\mathcal{C}_{i}$; since the set $\mathcal{I}_{\Lambda^{i}_{1}}$
contains at least the closure of the interior of $\mathcal{C}_{i}$, we have
that $\Gamma^{i}_{1}$ is $e_{i}$-smaller than $\Lambda^{i}_{1}$. We can hence
assume that $\Lambda^{i-1}_{1}$ lies outside $\mathcal{C}_{i}$ or that
$\mathcal{D}_{i}$ lies outside $\mathcal{C}_{i}$ (or both). Indeed, if both
$\Lambda^{i-1}_{1}$ and $\mathcal{D}_{i}$ lied inside $\mathcal{C}_{i}$, then
the first step of the algorithm would have constructed $\Lambda^{i}_{1}$, and
hence $\mathcal{R}^{i}_{1}$ would contain a single realization
$\Gamma^{i}_{1}$ added during the first step (note that $\Gamma^{i}_{1}$ would
not necessarily be the same as $\Lambda^{i}_{1}$, however the outer faces of
both $\Gamma^{i}_{1}$ and $\Lambda^{i}_{1}$ would be delimited by
$\mathcal{C}_{i}$).

Second, consider the case in which $\Lambda^{i-1}_{1}$ lies inside
$\mathcal{C}_{i}$ and $\mathcal{D}_{i}$ lies outside $\mathcal{C}_{i}$ in
$\Lambda^{i}_{1}$. This implies that the second step of the algorithm
constructs $\Lambda^{i}_{1}$, and hence $\mathcal{R}^{i}_{1}$ contains a
realization $\Gamma^{i}_{1}$ added during the second step of the algorithm.
The outer face of $\Gamma^{i}_{1}$ is bounded by the edges of
$\mathcal{C}_{i}$ and $\mathcal{D}_{i}$ different from $g_{i}$, same as
$\Lambda^{i}_{1}$, hence $\Gamma^{i}_{1}$ is $e_{i}$-smaller than
$\Lambda^{i}_{1}$.

Third, consider the case in which $\Lambda^{i-1}_{1}$ lies outside
$\mathcal{C}_{i}$. If $\mathcal{D}_{i}$ lies inside $\mathcal{C}_{i}$ in
$\Lambda^{i}_{1}$, or if $\mathcal{D}_{i}$ lies outside $\mathcal{C}_{i}$ in
$\Lambda^{i}_{1}$ and does not fit inside $\mathcal{C}_{i}$, then the third
step of the algorithm constructs $\Lambda^{i}_{1}$ and adds it to
$\mathcal{R}^{i}_{1}$. If $\mathcal{D}_{i}$ lies outside $\mathcal{C}_{i}$ in
$\Lambda^{i}_{1}$ and fits inside $\mathcal{C}_{i}$, then the third step of
the algorithm constructs a realization $\Gamma^{i}_{1}$ which coincides with
$\Lambda^{i}_{1}$ when restricted to $G^{i-1}_{1}\cup c_{i}$, but in which
$\mathcal{D}_{i}$ lies inside $\mathcal{C}_{i}$. Then we have that
$\Gamma^{i}_{1}$ is $e_{i}$-smaller than $\Lambda^{i}_{1}$. This concludes the
proof of the $e_{i}$-optimality of $\mathcal{R}^{i}_{1}$ and of the
correctness of the inductive step.

The inductive step is hence performed in $O(n^{2})$ time. Since there are
$O(n)$ inductive steps, our algorithm takes $O(n^{3})$ time in order to either
conclude that $G_{1}$ admits no $e_{x-1}$-outer realization or to construct an
$e_{x-1}$-optimal set $\mathcal{R}_{1}$ with $|\mathcal{R}_{1}|\in O(n)$ of
$e_{x-1}$-outer realizations of $G_{1}$ together with the plane embedding
$\mathcal{E}(\Gamma_{1})$ of each realization $\Gamma_{1}$ in
$\mathcal{R}_{1}$; the algorithm also takes $O(n^{3})$ time in order to either
conclude that $G_{2}$ admits no $e_{x}$-outer realization or to construct an
$e_{x}$-optimal set $\mathcal{R}_{2}$ with $|\mathcal{R}_{2}|\in O(n)$ of
$e_{x}$-outer realizations of $G_{2}$ together with the plane embedding
$\mathcal{E}(\Gamma_{2})$ of each realization $\Gamma_{2}$ in
$\mathcal{R}_{2}$.

As argued above, if $G_{1}$ admits no $e_{x-1}$-outer realization or $G_{2}$
admits no $e_{x}$-outer realization, then $G$ admits no planar straight-line
realization. Assume hence that $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ are
both non-empty. We independently consider each pair $(\Gamma_{1},\Gamma_{2})$
such that $\Gamma_{1}\in\mathcal{R}_{1}$ and $\Gamma_{2}\in\mathcal{R}_{2}$;
since $|\mathcal{R}_{1}|$ and $|\mathcal{R}_{2}|$ are both in $O(n)$, there
are $O(n^{2})$ such pairs. We construct eight straight-line realizations of
$G$, each with the corresponding plane embedding, according to the following
choices:

  * •

the vertices of $c_{x-1}$ and $c_{x}$ not incident to $e_{x-1}$ might lie on
the same side or on different sides of the line through $e_{x-1}$;

  * •

the vertices of $c_{x+1}$ and $c_{x}$ not incident to $e_{x}$ might lie on the
same side or on different sides of the line through $e_{x}$; and

  * •

the vertices of $d_{x}$ and $c_{x}$ not incident to $g_{x}$ might lie on the
same side or on different sides of the line through $g_{x}$.

We test in $O(n)$ time whether each of these straight-line realizations is
planar and respects the corresponding plane embedding, by means of Theorem
3.1. Hence, all these tests can be performed in overall $O(n^{3})$ time. If
(at least) one of these realizations is planar, then it is the desired planar
straight-line realization of $G$. Otherwise, there exists no planar straight-
line realization of $G$; this can be proved as in the proof of Theorem 6.1.
Namely, if a planar straight-line realization $\Gamma$ of $G$ exists, then the
restriction of $\Gamma$ to $G_{1}$ and the restriction of $\Gamma$ to $G_{2}$
can be replaced by straight-line realizations obtained by rigid
transformations of suitable realizations in $\mathcal{R}_{1}$ and
$\mathcal{R}_{2}$, respectively. By Lemma 21, this results in a planar
straight-line realization of $G$ which, by construction, is one of the
straight-line realizations for which the planarity testing was negative. This
contradiction concludes the proof of the theorem. ∎

##  7 2-Trees with Short Longest Path

In this section, we show that the FEPR problem is polynomial-time solvable for
weighted $2$-trees whose longest path has bounded length, where the length of
a path is the number of edges in it. Our algorithm actually runs in polynomial
time in a more general case: if the height of the SPQ-tree of the $2$-tree is
bounded. We start this section by introducing the necessary definitions and
notation.

The notion of SPQ-tree is a specialization of the well-known notion of SPQR-
tree [24, 31] for series-parallel graphs [23, 49]. A series-parallel graph is
any graph that can be obtained by means of the following recursive
construction (see Fig. 31).

Figure 31: A $2$-tree $G$ and its SPQ-tree $\mathcal{T}$. The gray regions
show $G_{\mu}$ and $\mathcal{T}_{\mu}$, for a node $\mu$ of $\mathcal{T}$. The
poles of $\mu$ are represented by empty disks in $G$. The fat edge corresponds
to the Q-node that is a child of the root of $\mathcal{T}$. The height of
$\mathcal{T}$ is $8$, the one of $\mathcal{T}_{\mu}$ is $4$.

  * •

An edge $(u,v)$ is a series-parallel graph with two poles $u$ and $v$; its
SPQ-tree $\mathcal{T}$ is rooted tree with a single Q-node. We say that
$(u,v)$ corresponds to the Q-node (and vice versa).

  * •

Let $G_{1},\dots,G_{k}$ be series-parallel graphs, where $G_{i}$ has poles
$u_{i}$ and $v_{i}$, for $i=1,\dots,k$; also, let
$\mathcal{T}_{1},\dots,\mathcal{T}_{k}$ be their SPQ-trees. The graph obtained
by identifying the vertices $u_{1},\dots,u_{k}$ into a single vertex $u$ and
the vertices $v_{1},\dots,v_{k}$ into a single vertex $v$ is a series-parallel
graph $G$ with poles $u$ and $v$. The SPQ-tree $\mathcal{T}$ of $G$ is the
tree whose root is a P-node which is the parent of the roots of
$\mathcal{T}_{1},\dots,\mathcal{T}_{k}$. We say that $G$ corresponds to
$\mathcal{T}$.

  * •

Let $G_{1},\dots,G_{k}$ be series-parallel graphs, where $G_{i}$ has poles
$u_{i}$ and $v_{i}$, for $i=1,\dots,k$; also, let
$\mathcal{T}_{1},\dots,\mathcal{T}_{k}$ be their SPQ-trees. The graph obtained
by identifying the vertex $v_{i}$ with the vertex $u_{i+1}$, for
$i=1,\dots,k-1$, is a series-parallel graph $G$ with poles $u_{1}$ and
$v_{k}$. The SPQ-tree $\mathcal{T}$ of $G$ is the tree whose root is an S-node
which is the parent of the roots of $\mathcal{T}_{1},\dots,\mathcal{T}_{k}$.
We say that $G$ corresponds to $\mathcal{T}$.

Every $2$-tree $G$ is a series-parallel graph (see, e.g., [13, Chapter 5])
such that:

  1. (C1)

The root of the SPQ-tree $\mathcal{T}$ of $G$ is a P-node.

  2. (C2)

Each P-node has at least two children; one of them is a Q-node and the others
are S-nodes.

  3. (C3)

Each S-node has exactly two children, each of which is either a Q-node or a
P-node.

Moreover, if $e$ is a prescribed edge of $G$, then the SPQ-tree of $G$ can be
constructed in such a way that the Q-node corresponding to $e$ is a child of
the root $\rho$ of the SPQ-tree (that is, $e$ is the edge between the poles of
$\rho$). We will use this property later.

Let $G$ be a $2$-tree, $\mathcal{T}$ be the SPQ-tree of $G$, and $\mu$ be a
node of $\mathcal{T}$. We denote by $u_{\mu}$ and $v_{\mu}$ the poles of
$\mu$, by $\mathcal{T}_{\mu}$ the subtree of $\mathcal{T}$ rooted at $\mu$,
and by $G_{\mu}$ the subgraph of $G$ corresponding to $\mathcal{T}_{\mu}$. The
height of $\mathcal{T}$ is the maximum number of edges in any root-to-leaf
path in $\mathcal{T}$. By Conditions (C1)–(C2), the height of $\mathcal{T}$ is
even and positive.

We can upper bound the height of an SPQ-tree of a $2$-tree $G$ in terms of the
length of the longest path of $G$, as proved in the following lemma.

######  Lemma 22.

Let $G$ be a $2$-tree, let $\ell$ be the length of the longest path of $G$,
let $\mathcal{T}$ be the SPQ-tree of $G$, and let $h$ be the height of
$\mathcal{T}$. Then we have $h\leq 2\ell-2$.

###### Proof.

We prove the following claim. For every P-node $\mu$ in $\mathcal{T}$, there
exists a path $P_{\mu}$ in $G_{\mu}$ that connects the poles $u$ and $v$ of
$\mu$ and whose length is $\frac{h_{\mu}}{2}+1$, where $h_{\mu}$ is the height
of $\mathcal{T}_{\mu}$. The claim implies the lemma by choosing $\mu$ to be
the root of $\mathcal{T}$; this can be done since, by Condition (C1), the root
of $\mathcal{T}$ is a P-node.

We prove the claim by induction on $h_{\mu}$. Recall that $h_{\mu}$ is even
and positive. Let $\nu$ be a child of $\mu$ such that the height of
$\mathcal{T}_{\nu}$ is $h_{\mu}-1$; by Condition (C2) and since $h_{\mu}\geq
2$, we have that $\nu$ is an S-node with poles $u$ and $v$. By Condition (C3),
we have that $\nu$ has two children $\nu_{1}$ and $\nu_{2}$, each of which is
either a P-node or a Q-node. Assume, w.l.o.g. up to a relabeling, that $u$ is
a pole of $\nu_{1}$, that $v$ is a pole of $\nu_{2}$, and that $w$ is the pole
shared by $\nu_{1}$ and $\nu_{2}$.

In the base case, we have $h_{\mu}=2$. Then $\nu_{1}$ and $\nu_{2}$ are both
Q-nodes, as otherwise the height of $\mathcal{T}$ would be greater than $2$.
It follows that $G$ contains the path $P_{\mu}=(u,w,v)$.

In the inductive case, we have $h_{\mu}>2$. Assume that the height of
$\mathcal{T}_{\nu_{1}}$ is $h_{\mu}-2$, as the case in which the height of
$\mathcal{T}_{\nu_{2}}$ is $h_{\mu}-2$ is analogous. Since $h_{\mu}>2$, we
have that $\nu_{1}$ is a P-node. By induction, $G_{\nu_{1}}$ contains a path
$\mathcal{P}_{\nu_{1}}$ with length $\frac{h_{\mu}-2}{2}+1$ between $u$ and
$w$. Further, $G_{\nu_{2}}$ contains the edge $(w,v)$; this is obvious if
$\nu_{2}$ is a Q-node and comes from Condition (C2) otherwise. The path
$\mathcal{P}_{\nu_{1}}\cup(w,v)$ is the desired path $\mathcal{P}_{\mu}$ with
length $\frac{h_{\mu}}{2}+1$ between $u$ and $v$. This completes the induction
and hence the proof of the lemma. ∎

The main result of this section is the following.

######  Theorem 7.1.

Let $G$ an $n$-vertex weighted $2$-tree, let $e^{*}$ be an edge of $G$ with
maximum length, let $\mathcal{T}$ be the SPQ-tree of $G$ such that the Q-node
corresponding to $e^{*}$ is a child of the root of $\mathcal{T}$, and let
$h^{*}$ be the height of $\mathcal{T}$. There exists an
$n^{O(2^{h^{*}})}$-time algorithm that tests whether $G$ admits a planar
straight-line realization and, in the positive case, constructs such a
realization.

Due to Lemma 22, Theorem 7.1 implies the following.

######  Corollary 1.

Let $G$ an $n$-vertex weighted $2$-tree and let $\ell$ be length of the
longest path of $G$. There exists an $n^{O(4^{\ell})}$-time algorithm that
tests whether $G$ admits a planar straight-line realization and, in the
positive case, constructs such a realization.

In the remainder of the section, we prove Theorem 7.1. Let $H$ be a $2$-tree
and let $(u,v)$ be an edge of $H$. A $uv$-external realization of $H$ is a
planar straight-line realization of $H$ such that both $u$ and $v$ are
incident to the outer face; note that the edge $(u,v)$ is not necessarily
incident to the outer face of a $uv$-external realization of $H$. Given two
$uv$-external realizations $\Gamma$ and $\Gamma^{\prime}$ of $H$, we say that
$\Gamma$ is $uv$-equivalent to $\Gamma^{\prime}$ if $\Gamma$ can be rotated
and translated (note that reflections are not allowed) so that the
representation of $(u,v)$ coincides with the one in $\Gamma^{\prime}$ and so
that the boundary of the outer face of $\Gamma$ coincides with the boundary of
the outer face of $\Gamma^{\prime}$. Given a set $\mathcal{R}$ of
$uv$-external realizations of $H$, we say that $\mathcal{R}$ is $uv$-complete
if, for every $uv$-external realization $\Gamma^{\prime}$ of $H$, there exists
a $uv$-external realization $\Gamma$ of $H$ in $\mathcal{R}$ such that
$\Gamma$ is $uv$-equivalent to $\Gamma^{\prime}$. Finally, a $uv$-complete set
$\mathcal{R}$ of $uv$-external realizations of $H$ is minimal if no
realization in $\mathcal{R}$ is $uv$-equivalent to a distinct realization in
$\mathcal{R}$.

As a first step of our algorithm, we compute the SPQ-tree $\mathcal{T}$ of $G$
such that the Q-node corresponding to $e^{*}$ is a child of the root $\rho$ of
$\mathcal{T}$; this can be done in $O(n)$ time [24, 31, 49]. One key point of
our algorithm is that, for every P-node $\mu$ of $\mathcal{T}$, we only need
to look for $u_{\mu}v_{\mu}$-external realizations of $G_{\mu}$ (recall that
$u_{\mu}$ and $v_{\mu}$ are the poles of $\mu$). This is formalized in the
following.

######  Lemma 23.

Let $\Gamma$ be any planar straight-line realization of $G$. For any P-node
$\mu$ of $\mathcal{T}$, the restriction $\Gamma_{\mu}$ of $\Gamma$ to
$G_{\mu}$ is a $u_{\mu}v_{\mu}$-external realization of $G_{\mu}$.

###### Proof.

Consider first the case in which $\mu=\rho$. Then $\Gamma_{\mu}$ coincides
with $\Gamma$. If $\Gamma$ were not a $u_{\mu}v_{\mu}$-external realization of
$G_{\mu}$, then $e^{*}$ would lie inside a $3$-cycle $c$ of $G$ in $\Gamma$.
However, this would contradict the planarity of $\Gamma$. Namely, since
$e^{*}$ is an edge with maximum length, the length of $e^{*}$ would be larger
than the one of each side of the triangle representing $c$ in $\Gamma$.

Consider now the case in which $\mu\neq\rho$. Suppose, for a contradiction,
that (at least) one of $u_{\mu}$ and $v_{\mu}$, say $u_{\mu}$, is not incident
to the outer face of $\Gamma_{\mu}$. Hence, $u_{\mu}$ lies inside a cycle $c$
of $G_{\mu}$ in $\Gamma_{\mu}$ and in $\Gamma$. Furthermore, at most one of
$u_{\rho}$ and $v_{\rho}$, say $u_{\rho}$, is a vertex of $c$ (if both
$u_{\rho}$ and $v_{\rho}$ would belong to $G_{\mu}$, we would have
$\mu=\rho$). Since $u_{\rho}$ and $v_{\rho}$ are incident to the outer face of
$\Gamma$, we have that $v_{\rho}$ lies outside $c$ in $\Gamma$. Since $G$ is
biconnected, it contains a path that connects $u_{\mu}$ with $v_{\rho}$ and
that does not contain vertices of $G_{\mu}$ other than $u_{\mu}$. By the
Jordan curve theorem, such a path crosses $c$ in $\Gamma$, a contradiction. ∎

For each P-node $\mu$ of $\mathcal{T}$, we construct an order
$\nu_{1},\dots,\nu_{k}$ of the children of $\mu$ as follows. First, we let
$\nu_{1}$ be the only Q-node that is a child of $\mu$; this node exists by
Condition (C2). We denote by $\lambda(\nu_{1})$ the length of the edge of $G$
corresponding to such a Q-node. Every other child $\nu_{i}$ of $\mu$ is an
S-node. Let $\sigma_{i}$ and $\tau_{i}$ be the two children of $\nu_{i}$; by
Condition (C3), each of them is either a Q-node or a P-node. We denote by
$w_{\nu_{i}}$ the pole that $\sigma_{i}$ and $\tau_{i}$ share (that is, their
pole different from $u_{\mu}$ and $v_{\mu}$); also, we can assume, w.l.o.g. up
to a relabeling of $\sigma_{i}$ with $\tau_{i}$, that $u_{\mu}$ is a pole of
$\sigma_{i}$ and $v_{\mu}$ is a pole of $\tau_{i}$. Then the edges
$(u_{\mu},w_{\nu_{i}})$ and $(v_{\mu},w_{\nu_{i}})$ belong to $G_{\nu_{i}}$,
as each of $\sigma_{i}$ and $\tau_{i}$ is either a Q-node (and then it
obviously contains the edge between its poles) or a P-node (and then it
contains the edge between its poles by Condition (C2)). Let $\lambda(\nu_{i})$
denote the sum of the lengths of the edges $(u_{\mu},w_{\nu_{i}})$ and
$(v_{\mu},w_{\nu_{i}})$. Then the order of the children of $\mu$ is
established so that
$\lambda(\nu_{1})\leq\lambda(\nu_{2})\leq\dots\leq\lambda(\nu_{k})$. Clearly,
such orders can be found for all the P-nodes of $\mathcal{T}$ in overall
$O(n\log n)$ time. For a P-node $\mu$ of $\mathcal{T}$ with children
$\nu_{1},\dots,\nu_{k}$ and for any $i\in\\{1,\dots,k\\}$, we denote by
$G^{i}_{\mu}$ the subgraph of $G_{\mu}$ which is the union of the graphs
$G_{\nu_{1}},\dots,G_{\nu_{i}}$. Observe that $G^{1}_{\mu}$ is the edge
$(u_{\mu},v_{\mu})$, while $G^{k}_{\mu}$ coincides with $G_{\mu}$.

Our algorithm either concludes that $G$ admits no planar straight-line
realization or constructs the following sets:

  * •

For each Q-node or P-node $\mu$, the algorithm constructs a non-empty minimal
$u_{\mu}v_{\mu}$-complete set $\mathcal{R}_{\mu}$ of $u_{\mu}v_{\mu}$-external
realizations of $G_{\mu}$. For each realization $\Gamma_{\mu}$ in
$\mathcal{R}_{\mu}$, the algorithm also constructs the plane embedding
$\mathcal{E}(\Gamma_{\mu})$.

  * •

For each P-node $\mu$ with children $\nu_{1},\dots,\nu_{k}$ and for each
$i=1,\dots,k$, the algorithm constructs a non-empty minimal
$u_{\mu}v_{\mu}$-complete set $\mathcal{R}^{i}_{\mu}$ of
$u_{\mu}v_{\mu}$-external realizations of $G^{i}_{\mu}$. For each realization
$\Gamma^{i}_{\mu}$ in $\mathcal{R}^{i}_{\mu}$, the algorithm also constructs
the plane embedding $\mathcal{E}(\Gamma^{i}_{\mu})$.

In order to construct such sets, the algorithm bottom-up visits all the
Q-nodes and all the P-nodes of $\mathcal{T}$.

When a Q-node $\mu$ is visited, the set $\mathcal{R}_{\mu}$ is defined as
$\\{\Gamma_{\mu}\\}$, where $\Gamma_{\mu}$ is the unique (up to rotation and
translation) straight-line realization of the edge of $G$ corresponding to
$\mu$. Obviously, $\mathcal{R}_{\mu}$ is a minimal $u_{\mu}v_{\mu}$-complete
set of $u_{\mu}v_{\mu}$-external realizations of $G_{\mu}$.

Suppose now that a P-node $\mu$ of $\mathcal{T}$ with children
$\nu_{1},\dots,\nu_{k}$ is considered. For $i=2,\dots,k$, since we already
visited the children $\sigma_{i}$ and $\tau_{i}$ of $\nu_{i}$, we have the
sets $\mathcal{R}_{\sigma_{i}}$ and $\mathcal{R}_{\tau_{i}}$ (indeed, if we
concluded that $G$ admits no planar straight-line realization, there is
nothing else to do). Our algorithm processes the children
$\nu_{1},\dots,\nu_{k}$ of $\mu$ in this order. For $i=1,\dots,k$, after
visiting $\nu_{i}$, the algorithm either concludes that $G$ admits no planar
straight-line realization or constructs the set $\mathcal{R}^{i}_{\mu}$. In
the latter case, for each realization $\Gamma^{i}_{\mu}$ in
$\mathcal{R}^{i}_{\mu}$, the algorithm also constructs the plane embedding
$\mathcal{E}(\Gamma^{i}_{\mu})$. If the algorithm constructs the set
$\mathcal{R}^{k}_{\mu}$, then we set
$\mathcal{R}_{\mu}=\mathcal{R}^{k}_{\mu}$.

We now describe how the algorithm processes the children
$\nu_{1},\dots,\nu_{k}$ of a P-node $\mu$. The algorithm starts by defining
$\mathcal{R}^{1}_{\mu}=\mathcal{R}_{\nu_{1}}$ (recall that $\nu_{1}$ is a
Q-node). Then, for $i=2,\dots,k$, it constructs the set
$\mathcal{R}^{i}_{\mu}$ by combining the realizations of $G^{i-1}_{\mu}$ in
$\mathcal{R}^{i-1}_{\mu}$ with the realizations of $G_{\sigma_{i}}$ in
$\mathcal{R}_{\sigma_{i}}$ and with the realizations of $G_{\tau_{i}}$ in
$\mathcal{R}_{\tau_{i}}$. This is done as follows.

We initialize $\mathcal{R}^{i}_{\mu}=\emptyset$. Then, for every triple of
realizations $\Gamma^{i-1}_{\mu}\in\mathcal{R}^{i-1}_{\mu}$,
$\Gamma_{\sigma_{i}}\in\mathcal{R}_{\sigma_{i}}$, and
$\Gamma_{\tau_{i}}\in\mathcal{R}_{\tau_{i}}$, we construct two straight-line
realizations $\Phi^{i}_{\mu}$ and $\Psi^{i}_{\mu}$ of $G^{i}_{\mu}$ (and two
plane embeddings $\mathcal{E}(\Phi^{i}_{\mu})$ and
$\mathcal{E}(\Psi^{i}_{\mu})$ of $G^{i}_{\mu}$) as follows. Recall that the
poles of $\sigma_{i}$ are $u_{\mu}$ and $w_{\nu_{i}}$, while the ones of
$\tau_{i}$ are $v_{\mu}$ and $w_{\nu_{i}}$. Refer to Figs. 32 and 33.

Figure 32: Construction of the realizations $\Phi^{i}_{\mu}$ and
$\Psi^{i}_{\mu}$ of $G^{i}_{\mu}$ from the realizations
$\Gamma^{i-1}_{\mu}\in\mathcal{R}^{i-1}_{\mu}$,
$\Gamma_{\sigma_{i}}\in\mathcal{R}_{\sigma_{i}}$, and
$\Gamma_{\tau_{i}}\in\mathcal{R}_{\tau_{i}}$. In this example, $i=4$; further,
$\Phi^{i}_{\mu}$ is planar and $\Psi^{i}_{\mu}$ is non-planar. Figure 33:
Construction of the plane embeddings $\mathcal{E}(\Phi^{i}_{\mu})$ and
$\mathcal{E}(\Psi^{i}_{\mu})$ of $G^{i}_{\mu}$ from the plane embeddings
$\mathcal{E}(\Gamma^{i-1}_{\mu})$, $\mathcal{E}(\Gamma_{\sigma_{i}})$, and
$\mathcal{E}(\Gamma_{\tau_{i}})$. The illustration is coherent with the
realizations of Fig. 32.

  * •

First, we initialize both $\Phi^{i}_{\mu}$ and $\Psi^{i}_{\mu}$ to
$\Gamma^{i-1}_{\mu}$.

  * •

Second, we place the vertex $w_{\nu_{i}}$ in $\Phi^{i}_{\mu}$ and
$\Psi^{i}_{\mu}$ with the two placements that realize the prescribed lengths
of the edges $(u_{\mu},w_{\nu_{i}})$ and $(v_{\mu},w_{\nu_{i}})$; in
particular, the placement of $w_{\nu_{i}}$ in $\Phi^{i}_{\mu}$ is such that
the clockwise order of the vertices of the cycle
$(u_{\mu},v_{\mu},w_{\nu_{i}})$ is $u_{\mu},w_{\nu_{i}},v_{\mu}$, while the
placement of $w_{\nu_{i}}$ in $\Psi^{i}_{\mu}$ is such that the clockwise
order of the vertices of the cycle $(u_{\mu},v_{\mu},w_{\nu_{i}})$ is
$u_{\mu},v_{\mu},w_{\nu_{i}}$.

  * •

Third, we insert $\Gamma_{\sigma_{i}}$ in $\Phi^{i}_{\mu}$ so that the
representation of the edge $(u_{\mu},w_{\nu_{i}})$ in $\Gamma_{\sigma_{i}}$
coincides with the one in $\Phi^{i}_{\mu}$. We also insert $\Gamma_{\tau_{i}}$
in $\Phi^{i}_{\mu}$ so that the representation of the edge
$(v_{\mu},w_{\nu_{i}})$ in $\Gamma_{\tau_{i}}$ coincides with the one in
$\Phi^{i}_{\mu}$. This concludes the construction of $\Phi^{i}_{\mu}$. The
insertion of $\Gamma_{\sigma_{i}}$ and $\Gamma_{\tau_{i}}$ in $\Psi^{i}_{\mu}$
in order to conclude the construction of $\Psi^{i}_{\mu}$ is done in the same
way.

  * •

Finally, we construct a plane embedding $\mathcal{E}(\Phi^{i}_{\mu})$ as
follows:

    * –

We glue the lists of the edges incident to $u_{\mu}$ in
$\mathcal{E}(\Gamma^{i-1}_{\mu})$ and $\mathcal{E}(\Gamma_{\sigma_{i}})$, so
that, in the counter-clockwise order of the edges incident to $u_{\mu}$, the
edge $e_{u}$ that enters $u_{\mu}$ when traversing in counter-clockwise order
the boundary of the outer face of $\mathcal{E}(\Gamma^{i-1}_{\mu})$ comes
immediately before the edge $g_{u}$ that enters $u_{\mu}$ when traversing in
clockwise order the boundary of the outer face of
$\mathcal{E}(\Gamma_{\sigma_{i}})$.

    * –

We glue the lists of the edges incident to $v_{\mu}$ in
$\mathcal{E}(\Gamma^{i-1}_{\mu})$ and $\mathcal{E}(\Gamma_{\tau_{i}})$, so
that, in the clockwise order of the edges incident to $v_{\mu}$, the edge
$e_{v}$ that enters $v_{\mu}$ when traversing in clockwise order the boundary
of the outer face of $\Gamma^{i-1}_{\mu}$ comes immediately before the edge
$g_{v}$ that enters $v_{\mu}$ when traversing in counter-clockwise order the
boundary of the outer face of $\Gamma_{\tau_{i}}$.

    * –

We let the cycle bounding the outer face of $\mathcal{E}(\Phi^{i}_{\mu})$ be
composed of the path that goes from $v_{\mu}$ to $u_{\mu}$ in clockwise
direction along the outer face of $\mathcal{E}(\Gamma^{i-1}_{\mu})$, of the
path that goes from $u_{\mu}$ to $w_{\nu_{i}}$ in clockwise direction along
the outer face of $\mathcal{E}(\Gamma_{\sigma_{i}})$, and of the path that
goes from $w_{\nu_{i}}$ to $v_{\mu}$ in clockwise direction along the outer
face of $\mathcal{E}(\Gamma_{\tau_{i}})$.

We remark that $\mathcal{E}(\Phi^{i}_{\mu})$ is not necessarily the plane
embedding of $\Phi^{i}_{\mu}$, in fact $\Phi^{i}_{\mu}$ might even be non-
planar.

A plane embedding $\mathcal{E}(\Psi^{i}_{\mu})$ is constructed analogously.

The straight-line realizations $\Phi^{i}_{\mu}$ and $\Psi^{i}_{\mu}$, together
with the plane embeddings $\mathcal{E}(\Phi^{i}_{\mu})$ and
$\mathcal{E}(\Psi^{i}_{\mu})$, are hence constructed in $O(n)$ time.

We remark that the plane embeddings $\mathcal{E}(\Phi^{i}_{\mu})$ and
$\mathcal{E}(\Psi^{i}_{\mu})$ both place $G_{\nu_{i}}$ “externally” with
respect to $G^{i-1}_{\mu}$. This is a main ingredient for bounding the running
time of our algorithm. It is also not a loss of generality, because of the
ordering that has been established for the children of $\mu$, as proved in the
following lemma.

######  Lemma 24.

Consider a $u_{\mu}v_{\mu}$-external realization $\Gamma^{i}_{\mu}$ of
$G^{i}_{\mu}$. Then the restriction of $\Gamma^{i}_{\mu}$ to $G_{\nu_{i}}$
lies in the outer face of the restriction of $\Gamma^{i}_{\mu}$ to
$G^{i-1}_{\mu}$.

###### Proof.

Suppose, for a contradiction, that the restriction of $\Gamma^{i}_{\mu}$ to
$G_{\nu_{i}}$ lies inside an internal face $f$ of the restriction of
$\Gamma^{i}_{\mu}$ to $G^{i-1}_{\mu}$. In particular, the path
$(u_{\mu},w_{\nu_{i}},v_{\mu})$ lies inside $f$ in $\Gamma^{i}_{\mu}$. Since
$\Gamma^{i}_{\mu}$ is a $u_{\mu}v_{\mu}$-external realization of
$G^{i}_{\mu}$, both $u_{\mu}$ and $v_{\mu}$ are incident to the outer face of
$\Gamma^{i}_{\mu}$, hence it is possible to draw a Jordan arc
$\mathcal{C}_{\mu}$ connecting $u_{\mu}$ and $v_{\mu}$ and lying in the outer
face of $\Gamma^{i}_{\mu}$, except at its end-points. Now $\mathcal{C}_{\mu}$
and the path $(u_{\mu},w_{\nu_{i}},v_{\mu})$ form a closed curve which
contains the edge $(u_{\mu},v_{\mu})$ on one side and a graph $G_{\nu_{j}}$ on
the other side (as otherwise $f$ would be the outer face of
$\Gamma^{i}_{\mu}$), for some $2\leq j<i$. However, this implies that the path
$(u_{\mu},w_{\nu_{i}},v_{\mu})$ lies inside the triangle representing the
$3$-cycle $(u_{\mu},w_{\nu_{j}},v_{\mu})$ in $\Gamma^{i}_{\mu}$. This
contradicts the planarity of $\Gamma^{i}_{\mu}$; indeed, we have
$\ell(\nu_{i})>\ell(\nu_{j})>\ell(\nu_{1})$, hence the length of the path
$(u_{\mu},w_{\nu_{i}},v_{\mu})$ is larger than the lengths of the path
$(u_{\mu},w_{\nu_{j}},v_{\mu})$ and of the edge $(u_{\mu},v_{\mu})$ in
$\Gamma^{i}_{\mu}$. ∎

We now resume the description of how the algorithm constructs
$\mathcal{R}^{i}_{\mu}$. By means of Theorem 3.1, we test in $O(n)$ time
whether $\Phi^{i}_{\mu}$ is a planar straight-line realization respecting
$\mathcal{E}(\Phi^{i}_{\mu})$. By the construction of
$\mathcal{E}(\Phi^{i}_{\mu})$, the test is positive if and only if
$\Phi^{i}_{\mu}$ is a $u_{\mu}v_{\mu}$-external realization of $G^{i}_{\mu}$.
If the test is negative, then we discard $\Phi^{i}_{\mu}$. Otherwise, for
every realization $\Lambda^{i}_{\mu}$ in $\mathcal{R}^{i}_{\mu}$, we test
whether $\Phi^{i}_{\mu}$ is $u_{\mu}v_{\mu}$-equivalent to $\Lambda^{i}_{\mu}$
and, if it is, we discard $\Phi^{i}_{\mu}$. This can be done in $O(n)$ time by
rotating and translating $\Phi^{i}_{\mu}$ so that the representation of the
edge $(u_{\mu},v_{\mu})$ coincides with the one in $\Lambda^{i}_{\mu}$ and by
then checking whether the vertices along on the boundary of the outer face of
$\Phi^{i}_{\mu}$ have the same coordinates as the vertices along on the
boundary of the outer face of $\Lambda^{i}_{\mu}$. If we did not discard
$\Phi^{i}_{\mu}$, then we insert it into $\mathcal{R}^{i}_{\mu}$.

We process $\Psi^{i}_{\mu}$ analogously to $\Phi^{i}_{\mu}$.

After we have processed every triple of drawings
$\Gamma^{i-1}_{\mu}\in\mathcal{R}^{i-1}_{\mu}$,
$\Gamma_{\sigma_{i}}\in\mathcal{R}_{\sigma_{i}}$, and
$\Gamma_{\tau_{i}}\in\mathcal{R}_{\tau_{i}}$, if the set
$\mathcal{R}^{i}_{\mu}$ is empty, then we report that $G$ admits no planar
straight-line realization, otherwise $\mathcal{R}^{i}_{\mu}$ is a minimal
$u_{\mu}v_{\mu}$-complete set of $u_{\mu}v_{\mu}$-external realizations of
$G^{i}_{\mu}$. The correctness of these conclusions is proved in the following
lemma.

######  Lemma 25.

If $\mathcal{R}^{i}_{\mu}$ is empty, then $G$ admits no planar straight-line
realization. Otherwise, $\mathcal{R}^{i}_{\mu}$ is a minimal
$u_{\mu}v_{\mu}$-complete set of $u_{\mu}v_{\mu}$-external realizations of
$G^{i}_{\mu}$.

###### Proof.

The main ingredient of the proof is the following claim: If $G^{i}_{\mu}$
admits a $u_{\mu}v_{\mu}$-external realization $\Lambda^{i}_{\mu}$, then
$\mathcal{R}^{i}_{\mu}$ contains a $u_{\mu}v_{\mu}$-external realization that
is $u_{\mu}v_{\mu}$-equivalent to $\Lambda^{i}_{\mu}$.

We prove the claim. For a contradiction, suppose that $G^{i}_{\mu}$ admits a
$u_{\mu}v_{\mu}$-external realization $\Lambda^{i}_{\mu}$ and that
$\mathcal{R}^{i}_{\mu}$ does not contain any $u_{\mu}v_{\mu}$-external
realization that is $u_{\mu}v_{\mu}$-equivalent to $\Lambda^{i}_{\mu}$. We are
going to replace parts of $\Lambda^{i}_{\mu}$ with realizations in
$\mathcal{R}^{i-1}_{\mu}$, $\mathcal{R}_{\sigma_{i}}$, and
$\mathcal{R}_{\tau_{i}}$, so to obtain a $u_{\mu}v_{\mu}$-external realization
of $G^{i}_{\mu}$ that is constructed by the algorithm and that should hence
have been inserted in $\mathcal{R}^{i}_{\mu}$ (unless a
$u_{\mu}v_{\mu}$-equivalent $u_{\mu}v_{\mu}$-external realization of
$G^{i}_{\mu}$ is already in $\mathcal{R}^{i}_{\mu}$), from which a
contradiction follows.

Let $\Lambda^{i-1}_{\mu}$, $\Lambda_{\sigma_{i}}$, and $\Lambda_{\tau_{i}}$ be
the restrictions of $\Lambda^{i}_{\mu}$ to $G^{i-1}_{\mu}$, $G_{\sigma_{i}}$,
and $G_{\tau_{i}}$, respectively. By Lemma 24, we have that
$\Lambda_{\sigma_{i}}$ and $\Lambda_{\tau_{i}}$ lie in the outer face of
$\Lambda^{i-1}_{\mu}$; furthermore, the fact that $\Lambda^{i}_{\mu}$ is a
$u_{\mu}v_{\mu}$-external realization directly implies that
$\Lambda_{\sigma_{i}}$ and $\Lambda^{i-1}_{\mu}$ lie in the outer face of
$\Lambda_{\tau_{i}}$ and that $\Lambda_{\tau_{i}}$ and $\Lambda^{i-1}_{\mu}$
lie in the outer face of $\Lambda_{\sigma_{i}}$.

Since $\mathcal{R}^{i-1}_{\mu}$ is a $u_{\mu}v_{\mu}$-complete set of
$u_{\mu}v_{\mu}$-external realizations of $G^{i-1}_{\mu}$, it follows that
there exists a $u_{\mu}v_{\mu}$-external realization
$\Gamma^{i-1}_{\mu}\in\mathcal{R}^{i-1}_{\mu}$ of $G^{i-1}_{\mu}$ that is
$u_{\mu}v_{\mu}$-equivalent to $\Lambda^{i-1}_{\mu}$. Analogously, there
exists a $u_{\mu}w_{\nu_{i}}$-external realization
$\Gamma_{\sigma_{i}}\in\mathcal{R}_{\sigma_{i}}$ of $G_{\sigma_{i}}$ that is
$u_{\mu}w_{\nu_{i}}$-equivalent to $\Lambda_{\sigma_{i}}$ and there exists a
$v_{\mu}w_{\nu_{i}}$-external realization
$\Gamma_{\tau_{i}}\in\mathcal{R}_{\tau_{i}}$ of $G_{\tau_{i}}$ that is
$v_{\mu}w_{\nu_{i}}$-equivalent to $\Lambda_{\tau_{i}}$.

We can now replace $\Lambda^{i-1}_{\mu}$ with $\Gamma^{i-1}_{\mu}$ in
$\Lambda^{i}_{\mu}$, after rotating and translating $\Gamma^{i-1}_{\mu}$ so
that the representation of the edge $(u_{\mu},v_{\mu})$ coincides with the one
in $\Lambda^{i}_{\mu}$. Since the boundary of the outer face of
$\Gamma^{i-1}_{\mu}$ coincides with the boundary of the outer face of
$\Lambda^{i-1}_{\mu}$ and since $\Lambda_{\sigma_{i}}$ and
$\Lambda_{\tau_{i}}$ lie in the outer face of $\Lambda^{i-1}_{\mu}$, it
follows that after the replacement $\Lambda^{i}_{\mu}$ remains a
$u_{\mu}v_{\mu}$-external realization of $G^{i}_{\mu}$ (in particular, it
remains planar) that is $u_{\mu}v_{\mu}$-equivalent to $\Lambda^{i}_{\mu}$. We
can analogously replace $\Lambda_{\sigma_{i}}$ with $\Gamma_{\sigma_{i}}$ and
$\Lambda_{\tau_{i}}$ with $\Gamma_{\tau_{i}}$, obtaining a
$u_{\mu}v_{\mu}$-external realization of $G_{\mu}$ that is constructed by the
algorithm and that is $u_{\mu}v_{\mu}$-equivalent to $\Lambda^{i}_{\mu}$. This
implies that $\mathcal{R}^{i}_{\mu}$ contains a $u_{\mu}v_{\mu}$-external
realization that is $u_{\mu}v_{\mu}$-equivalent to $\Lambda^{i}_{\mu}$, a
contradiction which proves the claim.

The claim directly implies that, if $\mathcal{R}^{i}_{\mu}$ is empty, then
$G^{i}_{\mu}$ admits no $u_{\mu}v_{\mu}$-external realization, hence $G_{\mu}$
admits no $u_{\mu}v_{\mu}$-external realization (given that $G^{i}_{\mu}$ is a
subgraph of $G_{\mu}$), and finally that $G$ admits no planar straight-line
realization, by Lemma 23.

Suppose now that $\mathcal{R}^{i}_{\mu}$ is non-empty. We prove that
$\mathcal{R}^{i}_{\mu}$ is a minimal $u_{\mu}v_{\mu}$-complete set of
$u_{\mu}v_{\mu}$-external realizations of $G^{i}_{\mu}$. First, that every
realization $\Gamma^{i}_{\mu}$ in $\mathcal{R}^{i}_{\mu}$ is
$u_{\mu}v_{\mu}$-external directly descends from the $O(n)$-time test that is
performed by means of Theorem 3.1 on $\Gamma^{i}_{\mu}$; indeed,