On Planar Straight-Line Dominance Drawings

The $st$-planar graph $G_n$ consists of the directed paths $(s=v_1,v_2,v_5)$, $(v_1,v_3,v_4,v_5)$, $(v_5,v_6,\mathrm{\dots },v_n=t)$, and of the edges $(v_1,v_6)$, $(v_3,v_6)$, $(v_3,v_7)$, and $(v_1,v_n)$. Fig 3(a) shows a planar dominance drawing of $G_n$ with $y(v_i)=i$, for $i=1,\mathrm{\dots },n$. Suppose, for a contradiction, that a planar straight-line dominance drawing $\mathrm{\Gamma }$ of $G_n$ exists with $y(v_i)=i$, for $i=1,\mathrm{\dots },n$. We prove that the plane embedding in $\mathrm{\Gamma }$ of the underlying graph of $G_n$ is the one in Fig 3(a), except, possibly, for the position of the edge $(s,t)$. Obviously, the path $(v_1,v_2,v_5,v_6,\mathrm{\dots },v_n)$ has a unique plane embedding. Since $v_2$ and $v_4$ are incomparable and , we have $x(v_4)\le x(v_2)$, hence the clockwise order of the vertices along the cycle $𝒞:=(v_1,v_3,v_4,v_5,v_2)$ is $v_1,v_3,v_4,v_5,v_2$. From that, we get that the edges $(v_3,v_6)$ and $(v_3,v_7)$ lie above the path $(v_3,v_4,v_5,v_6,v_7)$, and finally that the edge $(v_1,v_6)$ lies below the path $(v_1,v_2,v_5,v_6)$. For any distinct $i,j\in \{1,\mathrm{\dots },n\}$, let ${\mathrm{\ell }}_{i,j}$ be the ray starting at $v_i$ and passing through $v_j$. Since , we have $x(v_2)-x(v_1)>x(v_4)-x(v_3)$. Also, we have $y(v_2)-y(v_1)=y(v_4)-y(v_3)=1$. Hence, the ray ${\mathrm{\ell }}_{1,2}$ has smaller slope than the ray ${\mathrm{\ell }}_{3,4}$; that is, such rays diverge, see Fig 3(b). Since the ray ${\mathrm{\ell }}_{1,6}$ has smaller slope than ${\mathrm{\ell }}_{1,2}$, and since the ray ${\mathrm{\ell }}_{3,6}$ has larger slope than ${\mathrm{\ell }}_{3,4}$, it follows that ${\mathrm{\ell }}_{1,6}$ and ${\mathrm{\ell }}_{3,6}$ also diverge, while they meet at $v_6$, a contradiction which proves the theorem. Note that vertices $v_8,\mathrm{\dots },v_n$ only serve the purpose of creating an infinite graph family. $◀$

We can similarly show that one cannot, in general, prescribe the $x$-coordinates of a planar straight-line dominance drawing.

Also, we can strengthen Theorem 2 by proving that, for every $n\ge 10$ and for every sequence of $y$-coordinates, there exists an $st$-planar graph $G_n^{\prime }$ with vertex set $\{v_1,\mathrm{\dots },v_n\}$ such that there exists a planar dominance drawing of $G_n^{\prime }$ with $y(v_i)=y_i$, for $i=1,\mathrm{\dots },n$, and there exists no planar straight-line dominance drawing of $G_n^{\prime }$ with $y(v_i)=y_i$, for $i=1,\mathrm{\dots },n$. That is, the $y$-coordinates prescribed by Theorem 2 do not need to be uniformly distributed.

The key point for this is the observation that the proof of Theorem 2 works as long as $y(v_2)-y(v_1)\le y(v_4)-y(v_3)$. Hence, we can consider the four lines $y=y_i$, with $i=4,5,6,7$, and then distinguish two cases. If $y_5-y_4\le y_7-y_6$, we let our $st$-planar graph $G_n^{\prime }$ contain the graph $G_7$ from the proof of Theorem 2 and we set $y(v_i)=y_{i+3}$, for $i=1,\mathrm{\dots },7$, where $v_1,\mathrm{\dots },v_7$ is the vertex set of $G_7$. Otherwise, that is, if , we let our $st$-planar graph $G_n^{\prime }$ contain the graph obtained by reversing the edge directions of the graph $G_7$ and we set $y(v_i)=y_{8-i}$, for $i=1,\mathrm{\dots },7$, where $v_1,\mathrm{\dots },v_7$ is the vertex set of $G_7$.

Let $G$ be an $n$-vertex upper $st$-plane $3$-tree whose outer face is delimited by the cycle $(s,m,t)$. Let $\mathrm{\Delta }$ be any triangle with vertices $p_s,p_m,p_t$, where and . Also, let $D$ be a closed disk in the interior of $\mathrm{\Delta }$ such that, for any point $p$ in $D$, we have and ; see Figs 4(a) and 4(c). We prove by induction that $G$ admits a planar straight-line dominance drawing such that:

• $\mathrm{■}$

  $s$ lies at $p_s$, $m$ lies at $p_m$, and $t$ lies at $p_t$; and

• $\mathrm{■}$

  every internal vertex of $G$ lies in the interior of $D$.

The statement clearly implies the theorem. In the base case, in which $n=3$, the triangle $\mathrm{\Delta }$ is the required drawing of $G$ and the statement is trivially true.

Suppose now that $n>3$. Let $r$ be the first stacked vertex in the construction of $G$; that is, $r$ is the unique vertex of $G$ adjacent to $s$, $m$, and $t$. Note that the edge $(m,r)$ is directed away from $m$, given that $G$ is an upper $st$-plane $3$-tree. Let $G_1$, $G_2$, and $G_3$ be the subgraphs of $G$ inside the cycles $(s,m,r)$, $(s,r,t)$, and $(m,r,t)$, respectively. Note that $G_1$ is an upper $sr$-plane $3$-tree, $G_2$ is an upper $st$-plane $3$-tree, and $G_3$ is an upper $mt$-plane $3$-tree. Also, each of $G_1$, $G_2$, and $G_3$ has less than $n$ vertices. Let $p_r$ be any point inside $D$ and let ${\mathrm{\Delta }}_1$, ${\mathrm{\Delta }}_2$, and ${\mathrm{\Delta }}_3$ be the triangles $(p_s,p_m,p_r)$, $(p_s,p_r,p_t)$, and $(p_m,p_r,p_t)$, respectively. Place $r$ at $p_r$; by the properties of $D$, we have and , which complies with the orientation of $(m,r)$. Let $D_1$, $D_2$, and $D_3$ be closed disks such that (see Figs 4(b) and 4(d)):

• $\mathrm{■}$

  disk $D_1$ lies in the interior of ${\mathrm{\Delta }}_1\cap D$, disk $D_2$ lies in the interior of ${\mathrm{\Delta }}_2\cap D$, and disk $D_3$ lies in the interior of ${\mathrm{\Delta }}_3\cap D$;

• $\mathrm{■}$

  for any point $p\in D_2\cup D_3$, we have and ; and

• $\mathrm{■}$

  for any point $p_2\in D_2$ and any point $p_3\in D_3$, if the clockwise order of the vertices of $\mathrm{\Delta }$ is $p_s,p_t,p_m$, then we have and , otherwise we have and .

Clearly, disks $D_1$, $D_2$, and $D_3$ with the above properties always exist. By induction, $G_1$, $G_2$, and $G_3$ have planar straight-line dominance drawings ${\mathrm{\Gamma }}_1$, ${\mathrm{\Gamma }}_2$, and ${\mathrm{\Gamma }}_3$ with $s$, $m$, $r$, and $t$ drawn at $p_s$, $p_m$, $p_r$, and $p_t$, respectively, so that the internal vertices of $G_1$, $G_2$, and $G_3$ lie in the interior of $D_1$, $D_2$, and $D_3$, respectively. This results in a straight-line drawing $\mathrm{\Gamma }$ of $G$.

Since $p_r$, $D_1$, $D_2$, and $D_3$ lie in the interior of $D$, all the internal vertices of $G$ lie in the interior of $D$, as required. The upward planarity of $\mathrm{\Gamma }$ follows from the ones of ${\mathrm{\Gamma }}_1$, ${\mathrm{\Gamma }}_2$, and ${\mathrm{\Gamma }}_3$. In order to prove that $\mathrm{\Gamma }$ is a dominance drawing, consider any pair of vertices $u$ and $v$.

• $\mathrm{■}$

  If $u$ and $v$ belong to the same graph $G_i$, for some $i\in \{1,2,3\}$, then their placement complies with their dominance relationship, by induction.

• $\mathrm{■}$

  If one of $u$ and $v$ is $s$, say $u=s$, then $u$ is a predecessor of $v$, and indeed we have and . The case $u=t$ can be discussed similarly.

• $\mathrm{■}$

  If neither of $u$ and $v$ is $s$ or $t$, and one of $u$ and $v$ is $m$, say $u=m$, then $u$ is a predecessor of $v$, since $G$ is an upper $st$-plane $3$-tree. Since and , for any point $p\in D$, we have and .

• $\mathrm{■}$

  If $u$ is an internal vertex of $G_1$ and $v$ is an internal vertex of $G_2$ or $G_3$, then $u$ is a predecessor of $v$, since $G$ is an upper $st$-plane $3$-tree. Since, for any point $p\in D_1$ and any point $q\in D_2\cup D_3$, we have and , the placement of $u$ and $v$ complies with their dominance relationship.

• $\mathrm{■}$

  Finally, if $u$ is an internal vertex of $G_2$ and $v$ is an internal vertex of $G_3$, then $u$ and $v$ are incomparable, since $G$ is an upper $st$-plane $3$-tree. Since, for any point $p_2\in D_2$ and any point $p_3\in D_3$, we have and , or and , the placement of $u$ and $v$ complies with their dominance relationship.

This completes the induction and the proof of the theorem. $◀$

An analogous result holds true for $st$-plane $3$-trees such that, at every stacking operation, the edge that can be directed either way is always directed out of the newly inserted vertex.

Trying to use a similar strategy in order to construct a planar straight-line dominance drawing of every $st$-plane $3$-tree might be tempting. However, the “types” of internal vertices in a general $st$-plane $3$-tree are more than three. Namely, referring to the notation introduced in the proof of the theorem, the internal vertices of $G_2$ and $G_3$ are not all successors of $r$, but rather some are predecessors, some are successors, and some are incomparable to $r$. Hence, the “three-disks schema” fails, and more complex geometric invariants seem to be needed.

Let $G$ be an $n$-vertex sink-dominant $st$-plane $3$-tree whose outer face is delimited by the cycle $(s,m,t)$.

If $n>3$, then let $r$ be the internal vertex of $G$ adjacent to $s$, $m$ and $t$. If $r$ is a predecessor of $m$, as in Fig 5(a), we add a new source $s^{\prime }$ adjacent to $s$, $m$ and $t$ in the outer face of $G$, so that the outer face of the resulting graph $G^{\prime }$ is delimited by the $3$-cycle $(s^{\prime },s,t)$. Now $m$ is the internal vertex of $G^{\prime }$ adjacent to $s^{\prime }$, $s$ and $t$; furthermore, $m$ is a successor of $s$. Hence, by possibly adding a vertex and three edges to $G$ and changing some labels, we can assume w.l.o.g. that the internal vertex $r$ that is adjacent to the three vertices $s$, $m$ and $t$ incident to the outer face of our input $st$-plane $3$-tree $G$ is a successor of $m$.

The proof is similar in spirit to, however more involved than, the proof of Theorem 3. Let $\mathrm{\Delta }$ be any triangle with vertices $p_s$, $p_m$ and $p_t$, where and . If $p_m$ lies above the line through $p_s$ and $p_t$, we say that $\mathrm{\Delta }$ is of type A (see Fig 5(b)), otherwise it is of type B (see Fig 5(c)). Let $D$ and $E$ be closed disks contained in the interior of $\mathrm{\Delta }$ such that:

• $\mathrm{■}$

  if $\mathrm{\Delta }$ is of type A, then $D$ and $E$ are horizontally aligned, that is, they have the same two vertical tangents, while if $\mathrm{\Delta }$ is of type B, then $D$ and $E$ are vertically aligned;

• $\mathrm{■}$

  if $\mathrm{\Delta }$ is of type A, then $D$ is strictly below and to the right of $p_m$, while if $\mathrm{\Delta }$ is of type B, then $D$ is strictly above and to the left of $p_m$; and

• $\mathrm{■}$

  $E$ is strictly above and to the right of $p_m$.

We prove, by induction on $n$, that $G$ admits a planar straight-line dominance drawing such that:

• $\mathrm{■}$

  $s$ lies at $p_s$, $m$ lies at $p_m$, and $t$ lies at $p_t$;

• $\mathrm{■}$

  every internal vertex of $G$ that is a successor of $m$ lies in the interior of $E$; and

• $\mathrm{■}$

  every internal vertex of $G$ that is incomparable to $m$ lies in the interior of $D$.

Note that, because of the assumption that $r$ is a successor of $m$, no internal vertex of $G$ is a predecessor of $m$.

The statement clearly implies the theorem. In the base case, in which $n=3$, the triangle $\mathrm{\Delta }$ is the required drawing of $G$ and the statement is true. Suppose now that $n>3$. We only show the construction for the case in which $\mathrm{\Delta }$ is of Type B, as the other case is analogous.

Recall that $r$ is the unique vertex of $G$ adjacent to $s$, $m$ and $t$, and that the edge $(m,r)$ is directed towards $r$; refer to Fig 6.

Let $P_m:=(v_0=m,v_1,\mathrm{\dots },v_{\mathrm{\ell }}=r)$ be the longest directed path from $m$ to $r$. Since every vertex is adjacent to $t$ and since $r$ is a successor of $m$, we have that $P_m$ exists and is unique. For $j=1,\mathrm{\dots },\mathrm{\ell }$, let $M_j$ be the subgraph of $G$ induced by the vertices inside or on the boundary of the $3$-cycle $(v_{j-1},v_j,t)$ and note that $M_j$ is a sink-dominant $st$-plane $3$-tree. By the fact that $P_m$ is the longest directed path from $m$ to $r$, we have that, if $M_j$ contains internal vertices, then the internal vertex of $M_j$ that is adjacent to $v_{j-1}$, $v_j$ and $t$ is a successor of $v_j$. This implies that $M_j$ can be drawn recursively.

Also, let $P_s:=(u_0=s,u_1,\mathrm{\dots },u_k=r)$ be the longest directed path from $s$ to $r$ in $G$ that does not pass through $m$. For $i=1,\mathrm{\dots },k$, the subgraph $S_i$ of $G$ induced by the vertices inside or on the boundary of the $3$-cycle $(u_{i-1},u_i,t)$ is a sink-dominant $st$-plane $3$-tree. Further, if $S_i$ contains internal vertices, then the internal vertex of $S_i$ that is adjacent to $u_{i-1}$, $u_i$ and $t$ is a successor of $u_i$, hence $S_i$ can be drawn recursively.

Since every vertex of $G$ is adjacent to $t$, the interior of the cycle ${𝒞}_{sm}:=P_s\cup P_m\cup (s,m)$ does not contain any vertices, while it might contain some edges (and in fact it does, unless ${𝒞}_{sm}=(s,m,r)$). We are going to draw ${𝒞}_{sm}$ as a convex curve (hence the edges in its interior will not cause crossings).

We now draw $P_s$ and $P_m$. We also draw disks inside the triangles representing the cycles $(u_{i-1},u_i,t)$, for $i=1,\mathrm{\dots },k$, and $(v_{j-1},v_j,t)$, for $j=1,\mathrm{\dots },\mathrm{\ell }$, so that induction can be applied in order to draw the subgraphs $S_i$ and $M_j$ recursively. Refer to Fig 7 for an illustration of the relative placement of the vertices of $P_s$ and $P_m$ and of the desired disks.

We start by placing $r$ at the center of the disk $E$. Next, we draw the vertices $u_1,\mathrm{\dots },u_{k-1}$ in this order inside $D$. Let ${\sigma }_r$ be the intersection of the horizontal line ${\mathrm{\ell }}_r$ through $r$ with $D$, and let $d_1$ and $d_2$ be the leftmost and rightmost endpoints of ${\sigma }_r$, respectively. For $i=1,\mathrm{\dots },k-1$, by drawing $u_i$, we complete the drawing of the triangle ${\mathrm{\Delta }}_i^u$ representing cycle $(u_{i-1},u_i,t)$. Then we also place suitable disks $D_i^u$ and $E_i^u$ inside ${\mathrm{\Delta }}_i^u$ so that $S_i$ can be drawn recursively.

When we have to draw $u_i$, for some $i\in \{1,\mathrm{\dots },k-1\}$, we assume that (see Fig 8):

• $\mathrm{■}$

  (C1) the polygonal line $(u_0,\mathrm{\dots },u_{i-1},r)$ is convex and lies below ${\mathrm{\ell }}_r$;

• $\mathrm{■}$

  (C2) if $i>1$, the line through $u_{i-2}$ and $u_{i-1}$ cuts ${\sigma }_r$ in its interior, at a point $p_i$;

• $\mathrm{■}$

  (C3) if $i>1$, the segment between $u_{i-1}$ and $t$ cuts ${\sigma }_r$ in its interior, at a point $q_i$; and

• $\mathrm{■}$

  (C4) if $i>1$, the disks $D_{i-1}^u$ and $E_{i-1}^u$ lie inside $D$ and above ${\mathrm{\ell }}_r$.

We denote by $e_i$ be the rightmost point of $E_{i-1}^u$. Note that conditions (C1)–(C4) are vacuous if $i=1$ (i.e., before drawing $u_1$). In that case, for the sake of simplicity of the description, we let $p_i$, $q_i$, and $e_i$ coincide with $d_1$.

We now explain how to draw $u_i$. Let $\overline{x}=\max \{x(p_i),x(q_i),x(e_i)\}$, let $\tilde{x}=(x(d_2)+\overline{x})/2$, where , and let $\tilde{p}$ be the point of ${\sigma }_r$ with $x(\tilde{p})=\tilde{x}$. We place $u_i$ at $(\tilde{x},y(r)-ϵ)$, where $ϵ>0$ is sufficiently small so that conditions (C1)–(C3) are satisfied when we have to draw $u_{i+1}$. Indeed, if $ϵ=0$, then $u_i$ would be placed at $\tilde{p}$ and conditions (C1)–(C3) would be trivially satisfied when we have to draw $u_{i+1}$, hence they are also satisfied for some sufficiently small $ϵ>0$, by continuity.

We now place the disks $D_i^u$ and $E_i^u$ so that they have radius $\delta$ and centers at $(\tilde{x}\pm {ϵ}^{\prime },y(r)+{ϵ}^{\prime })$, where ${ϵ}^{\prime }>\delta >0$ are sufficiently small so that:

• $\mathrm{■}$

  $D_i^u$ and $E_i^u$ lie inside the triangle ${\mathrm{\Delta }}_i^u=(u_{i-1},u_i,t)$;

• $\mathrm{■}$

  $D_i^u$ and $E_i^u$ are lower than $D_{i-1}^u$ and $E_{i-1}^u$; and

• $\mathrm{■}$

  condition (C4) is satisfied when we have to draw $u_{i+1}$.

Indeed, if ${ϵ}^{\prime }=\delta =0$ such disks would degenerate and coincide with $\tilde{p}$, which is inside $D$ and also inside ${\mathrm{\Delta }}_i^u$, as the segment $\overline{u_{i-1}t}$ cuts ${\sigma }_r$ at a point $q_i$ to the left of $\tilde{p}$ and the segment $\overline{u_{i}t}$ cuts ${\sigma }_r$ at a point to the right of $\tilde{p}$. Hence, such disks remain inside $D$ and ${\mathrm{\Delta }}_i^u$ if ${ϵ}^{\prime }>\delta >0$ is sufficiently small, by continuity. Since ${ϵ}^{\prime }>\delta$, disks $D_i^u$ and $E_i^u$ lie above ${\mathrm{\ell }}_r$, hence ensuring condition (C4). Finally, choosing $\delta +{ϵ}^{\prime }$ smaller than the distance between $E_{i-1}^u$ and ${\mathrm{\ell }}_r$ ensures that $D_i^u$ and $E_i^u$ are lower than $D_{i-1}^u$ and $E_{i-1}^u$.

We now draw the vertices $v_1,\mathrm{\dots },v_{\mathrm{\ell }-1}$ in this order. For $j=1,\mathrm{\dots },\mathrm{\ell }-1$, when we draw $v_j$, we have drawn the triangle ${\mathrm{\Delta }}_j^v$ representing cycle $(v_{j-1},v_j,t)$. Then we also show how to place suitable disks $D_j^v$ and $E_j^v$ inside ${\mathrm{\Delta }}_j^v$ so that $M_j$ can be drawn recursively. This is done very similarly to the way vertices $u_1,\mathrm{\dots },u_{k-1}$ and disks $D_1^u,E_1^u,\mathrm{\dots },D_{k-1}^u,E_{k-1}^u$ were drawn (see again Fig 7), so we only highlight the differences here.

• $\mathrm{■}$

  First, all such vertices and disks lie inside $E$, rather than inside $D$.

• $\mathrm{■}$

  Second, the role previously played by ${\sigma }_r$ is now played by a segment ${\sigma }_r^{\prime }$ along the vertical line ${\mathrm{\ell }}_r^{\prime }$ through $r$. The endpoints of ${\sigma }_r^{\prime }$ are the lowest intersection point $e_1$ of ${\mathrm{\ell }}_r^{\prime }$ with the boundary of $E$ and the intersection point of ${\mathrm{\ell }}_r^{\prime }$ with the horizontal line through $u_1$. This is because the vertices $v_1,\mathrm{\dots },v_{\mathrm{\ell }-1}$ and the disks $D_1^v,E_1^v,\mathrm{\dots },D_{\mathrm{\ell }-1}^v,E_{\mathrm{\ell }-1}^v,D_{\mathrm{\ell }}^v$ have to be placed below (and to the right of) $u_1,\mathrm{\dots },u_{k-1}$, so to satisfy the constraints of a dominance drawing. When a vertex $v_j$ is drawn, the segment $\overline{v_{j}t}$ crosses the interior of ${\sigma }_r^{\prime }$.

• $\mathrm{■}$

  Third, the triangles ${\mathrm{\Delta }}_j^v$ are of Type A, unlike the triangles ${\mathrm{\Delta }}_i^u$ which are of Type B. Hence, the disks $D_j^v$ and $E_j^v$ are horizontally aligned, to the right of ${\sigma }_r^{\prime }$. The disks $D_j^v$ and $E_j^v$ are above and to the left of the disks $D_{j-1}^v$ and $E_{j-1}^v$.

After the vertices $v_1,\mathrm{\dots },v_{\mathrm{\ell }-1}$ and the disks $D_1^v,E_1^v,\mathrm{\dots },D_{\mathrm{\ell }-1}^v,E_{\mathrm{\ell }-1}^v$ have been drawn, it only remains to draw the disks $D_k^u$ and $E_k^u$ inside ${\mathrm{\Delta }}_k^u=(u_{k-1},u_k,t)$ and the disks $D_{\mathrm{\ell }}^v$ and $E_{\mathrm{\ell }}^v$ inside ${\mathrm{\Delta }}_{\mathrm{\ell }}^v=(v_{\mathrm{\ell }-1},v_{\mathrm{\ell }},t)$. See Fig 9. We have to place $D_k^u$ and $E_k^u$ above ${\sigma }_r$ and below $E_{k-1}^u$, with $D_k^u$ in $D$ and $E_k^u$ in $E$; also, $E_k^u$ has to be to the right of $r$. Analogously, we have to place $D_{\mathrm{\ell }}^v$ and $E_{\mathrm{\ell }}^v$ in $E$, to the right of ${\sigma }_r^{\prime }$ and to the left of $E_{\mathrm{\ell }-1}^v$, with $E_{\mathrm{\ell }}^v$ above $r$. Finally, $E_k^u$ has to be above and to the left of $E_{\mathrm{\ell }}^v$.

We can again use continuity arguments to prove that such disk placements exist. Indeed, $\overline{u_{k-1}t}$ cuts the interior of ${\sigma }_r$, hence $D_k^u$ can be initially set to be a point in the interior of ${\sigma }_r$, to the right of $\overline{u_{k-1}t}$. Analogously, $D_{\mathrm{\ell }}^v$ can be initially set to be a point in the interior of ${\sigma }_r^{\prime }$ above $\overline{v_{\mathrm{\ell }-1}t}$. Disks $E_k^u$ and $E_{\mathrm{\ell }}^v$ are initially set to coincide with $r$. Now $D_k^u$ and $E_k^u$ can be moved upward of a sufficiently small distance so that $D_k^u$ does not collide with $\overline{u_{k-1}t}$ and remains below $E_{k-1}^u$; note that now $D_k^u$ and $E_k^u$ are in the interior of ${\mathrm{\Delta }}_k^u$. Analogously, disks $D_{\mathrm{\ell }}^v$ and $E_{\mathrm{\ell }}^v$ can be moved rightward, of a sufficiently small distance so that they still are to the left of $E_{\mathrm{\ell }-1}^v$ and they now both lie in the interior of ${\mathrm{\Delta }}_{\mathrm{\ell }}^v$. Next, we move $E_k^u$ rightward and $E_{\mathrm{\ell }}^v$ upward so that they are to the right and above $r$, respectively. This movement is sufficiently small so that $E_k^u$ remains in ${\mathrm{\Delta }}_k^u$ and $E_{\mathrm{\ell }}^v$ in ${\mathrm{\Delta }}_{\mathrm{\ell }}^v$, and so that $E_k^u$ remains above and to the left of $E_{\mathrm{\ell }}^v$. Finally, we enlarge the disks so that they have a positive radius. Such a radius can be set to be sufficiently small so that all the above listed properties, which were satisfied before such an enlargement, are still maintained.

The drawing $\mathrm{\Gamma }$ of $G$ is completed by drawing the subgraphs $M_1,\mathrm{\dots },M_{\mathrm{\ell }}$, $S_1,\mathrm{\dots },S_k$ recursively, with triangles ${\mathrm{\Delta }}_1^v,\mathrm{\dots },{\mathrm{\Delta }}_{\mathrm{\ell }}^v,{\mathrm{\Delta }}_1^u,\mathrm{\dots },{\mathrm{\Delta }}_k^u$ representing their outer faces, and with disks $D_1^v,E_1^v,\mathrm{\dots },D_{\mathrm{\ell }}^v,E_{\mathrm{\ell }}^v,\mathrm{\dots },D_1^u,E_1^u,\mathrm{\dots },D_k^u,E_k^u$ inside such triangles.

The drawing $\mathrm{\Gamma }$ is straight-line by construction.

The drawings of the subgraphs $M_1,\mathrm{\dots },M_{\mathrm{\ell }},S_1,\mathrm{\dots },S_k$ are planar by induction. Moreover, the construction guarantees that the cycle ${𝒞}_{sm}$ is represented by a convex curve which keeps in its exterior every edge from a vertex of ${𝒞}_{sm}$ to $t$. It follows that distinct subgraphs among $M_1,\mathrm{\dots },M_{\mathrm{\ell }},S_1,\mathrm{\dots },S_k$ do not cross each other, that the edges inside or on the boundary of ${𝒞}_{sm}$ do not cross the subgraphs $M_1,\mathrm{\dots },M_{\mathrm{\ell }},S_1,\mathrm{\dots },S_k$, and that the edges inside or on the boundary of ${𝒞}_{sm}$ do not cross each other. Hence, $\mathrm{\Gamma }$ is planar.

Finally, we prove that $\mathrm{\Gamma }$ is a dominance drawing.

• $\mathrm{■}$

  Vertices that are internal to the same subgraph among $M_1,\mathrm{\dots },M_{\mathrm{\ell }},S_1,\mathrm{\dots },S_k$ are in the correct dominance relationship, by induction.

• $\mathrm{■}$

  Vertices that are internal to distinct subgraphs among $M_1,\mathrm{\dots },M_{\mathrm{\ell }},S_1,\mathrm{\dots },S_k$ are incomparable. This is because, for any internal vertex $v$ of a subgraph $M_j$ or $S_i$, we have that $t$ is the only vertex incident to the outer face of $M_j$ or $S_i$, respectively, that is a successor of $v$, as a consequence of the fact that $P_s$ and $P_m$ are the longest paths between their end-vertices. By induction, vertices that are internal to distinct subgraphs among $M_1,\mathrm{\dots },M_{\mathrm{\ell }},S_1,\mathrm{\dots },S_k$ are placed into disks among $D_1^v,E_1^v,\mathrm{\dots },D_{\mathrm{\ell }}^v,E_{\mathrm{\ell }}^v,D_1^u,E_1^u,\mathrm{\dots },D_k^u,$ $E_k^u$. Also, any two disks associated to distinct subgraphs among $M_1,\mathrm{\dots },M_{\mathrm{\ell }},S_1,\mathrm{\dots },S_k$ are one to the left and above the other one, hence such vertices are in the correct dominance relationship.

• $\mathrm{■}$

  By construction, $v_1,\mathrm{\dots },v_{\mathrm{\ell }-1}$ are to the right and below $u_1,\mathrm{\dots },u_{k-1}$, which is the correct dominance relationship as any vertex among $v_1,\mathrm{\dots },v_{\mathrm{\ell }-1}$ is incomparable with any vertex among $u_1,\mathrm{\dots },u_{k-1}$.

• $\mathrm{■}$

  Also by construction, we have that $v_j$ is above and to the right of $v_{j-1}$, for $j=1,\mathrm{\dots },\mathrm{\ell }$, and that $u_i$ is above and to the right of $u_{i-1}$, for $i=1,\mathrm{\dots },\mathrm{\ell }$, which is the correct dominance relationship because of the existence of the directed paths $P_s$ and $P_m$.

• $\mathrm{■}$

  Each vertex $u_i$ with $i=1,\mathrm{\dots },k$ is below and to the right of every disk among $D_1^u,E_1^u,\mathrm{\dots },D_i^u$ and is below and to the left of every disk among $E_i^u,D_{i+1}^u,\mathrm{\dots },D_k^u,E_k^u$; this is indeed the correct dominance relationship, as all the vertices in the former sequence of disks are incomparable to $u_i$, while all the vertices in the latter sequence of disks are successors of $u_i$. That the vertices among $v_1,\mathrm{\dots },v_{\mathrm{\ell }}$ are in the correct dominance relationship with respect to vertices inside disks $D_1^v,E_1^v,\mathrm{\dots },D_{\mathrm{\ell }}^v,E_{\mathrm{\ell }}^v$ can be argued similarly.

• $\mathrm{■}$

  Each vertex $u_i$ with $i=1,\mathrm{\dots },k-1$ is above and to the left of every disk among $D_1^v,E_1^v,\mathrm{\dots },D_{\mathrm{\ell }}^v$; this is indeed the correct dominance relationship, as $u_i$ is incomparable to every vertex internal to a subgraph $M_j$ with $j=1,\mathrm{\dots },\mathrm{\ell }$, with the exception of the successors of $r$ in $M_{\mathrm{\ell }}$, which are also successors of $u_i$; these vertices are in $E_{\mathrm{\ell }}^v$, which is indeed above and to the right of $u_i$. Similarly, each vertex $v_j$ with $j=1,\mathrm{\dots },\mathrm{\ell }-1$ is in the correct dominance relationship with respect to every vertex internal to a subgraph $S_i$ with $i=1,\mathrm{\dots },k$.

$◀$

Clearly, an analogous result holds true for $st$-plane $3$-trees in which the source is adjacent to every vertex.