11institutetext:  University of Perugia – 11email:
<EMAIL_ADDRESS>22institutetext: Universität
Tübingen – 22email<EMAIL_ADDRESS>33institutetext: Utrecth
University – 33email<EMAIL_ADDRESS>44institutetext: National Technical
U. of Athens – 44email<EMAIL_ADDRESS>55institutetext: TU Wien –
55email<EMAIL_ADDRESS>
# On 1-bend Upward Point-set
Embeddings of $st$-digraphs

Emilio Di Giacomo 11 Henry Förster 22 Daria Kokhovich 33 Tamara Mchedlidze 33
Fabrizio Montecchiani 11 Antonios Symvonis 44 Anaïs Villedieu 55

###### Abstract

We study the upward point-set embeddability of digraphs on one-sided convex
point sets with at most 1 bend per edge. We provide an algorithm to compute a
1-bend upward point-set embedding of outerplanar $st$-digraphs on arbitrary
one-sided convex point sets. We complement this result by proving that for
every $n\geq 18$ there exists a $2$-outerplanar $st$-digraph $G$ with $n$
vertices and a one-sided convex point set $S$ so that $G$ does not admit a
1-bend upward point-set embedding on $S$.

##  1 Introduction

A _point-set embedding (PSE)_ of a planar graph $G=(V,E)$ on a given set of
points $S$, with $|S|=|V|$, is a planar drawing $\Gamma$ of $G$ such that
every vertex of $G$ is represented by a point of $S$ and each edge is drawn as
a polyline connecting its end-vertices; if every edge has at most $b\geq 0$
bends, $\Gamma$ is a $b$-bend PSE.

Gritzmann et al. [22] proved that the class of graphs that admit a PSE without
bends along the edges on _every_ set of points in general position coincides
with the class of outerplanar graphs. Efficient algorithms to compute a PSE
with no bends on any _given_ set of points in general position exist for
outerplanar graphs [9] and trees [10]. Cabello [11] proved that deciding
whether a planar graph admits a PSE without bends on a _given_ set of points
is NP-complete. When bends are allowed, Kaufmann and Wiese [26] proved that
every planar graph admits a PSE on every set of points with at most two bends
per edge.

An _upward point-set embedding (UPSE)_ of a directed graph $G=(V,E)$ on a
given set of points $S$, with $|S|=|V|$, is a PSE with the additional property
that each edge $e$ is represented as a polyline monotonically increasing in
the $y$-direction; also in this case we say that $\Gamma$ is a $b$-bend UPSE
if every edge has at most $b$ bends. Clearly, for an UPSE to exist $G$ must be
an upward planar graph (and thus it must be a DAG). Different to the
undirected case, a characterization of the upward planar digraphs that admit a
UPSE without bends on _every_ point set is still missing even for points in
convex position. On the other hand, Binucci et al. [8] characterize DAGs that
admit a 1-bend UPSE on every _upward one-sided convex_ (UOSC) point set, i.e.,
a convex point set such that the bottommost point and the topmost point are
adjacent in the convex hull of $S$; the same class has also been characterized
by Heath and Pemmaraju [23] as the class of graphs that admit an upward 1-page
book embedding. For points in convex position Binucci et al. [8] proved that
there exist directed trees that do not admit an UPSE on every convex point set
and many partial results exists about the embeddability of specific subclasses
of directed trees on point sets with different properties [2, 3, 8, 25].
Kaufmann et al. [25] studied the problem of deciding whether an upward planar
graph admits an UPSE on a given set of points $S$ and show that the problem
can be solved in polynomial time for convex point sets, while it is NP-
complete for point sets in general position. Arseneva et al. [3] proved that
the problem remains NP-complete even for trees if one vertex is mapped to a
specific point. As for the undirected case, two bends per edge suffice for
UPSEs of upward planar graphs on any given set of points [21].

The results about (U)PSEs with zero and two bends naturally motivates the
study of (U)PSEs with one bend. Testing whether a (upward) planar graph admits
a 1-bend (U)PSE is NP-complete in both the upward and the non-upward variants.
Indeed, it is easy to see that a 1-bend (U)PSE on a set of collinear points
is, in fact, a 2-page (upward) book embedding and deciding whether a (upward)
planar graph $G$ admits a $2$-page (upward) book embedding is NP-complete both
in the non-upward [6] and in the upward case [5]. However, this relation
between 1-bend (U)PSEs and 2-page (upward) book embeddings relies on the use
of collinear points, and thus it does not hold for points in general or in
convex position. The following problems are therefore open and worth to
investigate.

###### Problem 1

Does every (upward) planar graph admit a $1$-bend (U)PSE on every set of
points in general or in convex position?

###### Problem 2

What is the complexity of testing whether a (upward) planar graph admits a
$1$-bend (U)PSE on a given set of points in general or in convex position?

We study the upward version of Problem 1 and our contribution is as follows.

  * •

On the positive side, we show that every $st$-outerplanar graph (i.e., an
outerplanar DAG with a single source and a single sink) admits a $1$-bend UPSE
on every UOSC point set (Theorem 4.1).

  * •

We give a negative answer to the upward version of Problem 1 (Theorem 5.1).
Namely, we prove that for every $n\geq 18$ there exists a $2$-outerplanar
$st$-digraph $G$ with $n$ vertices and an UOSC point set $S$ such that $G$
does not admit an UPSE on $S$ with at most one bend per edge.

Concerning our second contribution, Di Giacomo et al. [14] proved that every
two-terminal series-parallel digraph admits a $1$-bend UPSE on any given set
of points. This result has been extended by Mchedlidze and Symvonis [29] to
the superclass of $N$-free graphs111The embedded $N$-graph is shaped like an
N, i.e., it contains four vertices $a,b,c,d$ and three edges $(a,b)$, $(c,b)$
and $(c,d)$ such that (1) $(a,b)$ enters $b$ to the left of $(c,b)$ and (2)
$(c,b)$ exists $c$ to the left of $(c,d)$. An embedded $N$-free graph does not
contain the embedded $N$-graph as a subgraph.. However, there exist
$st$-outerplanar graphs that are not $N$-free digraphs (indeed,
$st$-outerplanar graphs may contain the forbidden $N$-digraph), and vice-
versa. We remark that the study of PSEs is a classical subject of
investigation in the Graph Drawing and Computational Geometry literature where
different (not necessarily upward) variants have been studied [1, 4, 12, 13,
15, 16, 17, 18, 20, 24, 28, 31]. In particular, Everett et al. [19] and
Löffler and Tóth [27] considered universal point sets for non-upward 1-bend
drawings.

The paper is organized as follows. In Section 2 we give preliminary
definitions. In Section 3 we prove necessary and sufficient conditions for the
existence of a $1$-bend UPSE. In Section 4 we describe the construction for
outerplanar digraphs, while our negative example is described in Section 5.
Open problems are in Section 6. Proofs marked with ($\star$) are sketched or
removed.

##  2 Preliminaries

Figure 1:  (a) Two edges that cross; (b) two edges that nest; (c) an example
of a 2UBE; (d) an example of a 2UTBE; the bold edges have spine crossings,
shown with small crosses; (e) removal of unnecessary sub-edges.

Let $G=(V,E)$ be an upward planar graph. A _$2$ -page upward book embedding_
(2UBE) of $G$ consists of a total order $\prec$ of $V$, that is, a topological
sorting of $G$, and of a partition of $E$ into two sets, called _pages_ , such
that no two edges cross; two edges $(u,v)$ with $u\prec v$ and $(w,z)$ with
$w\prec z$ _cross_ if the two edges are in the same page and $u\prec w\prec
v\prec z$ or $w\prec u\prec z\prec v$ (see Fig. 1). Also, edges $(u,v)$ and
$(w,z)$ _nest_ if they are on the same page and $u\prec w\prec z\prec v$ or
$w\prec u\prec v\prec z$ (see Fig. 1). We write $u\preceq v$ if $u$ precedes
or coincides with $v$. A 2UBE can be visualized as an upward planar drawing
such that all vertices of $G$ lie along a horizontal line $\ell$, called the
_spine_ , and each edge is represented as a semi-circle oriented in the
direction of the spine and completely contained either above the spine (_top
page_) or below the spine (_bottom page_). See Fig. 1 for an example of a
2UBE. A _$2$ -page upward topological book embedding_ (2UTBE) of $G$ is a 2UBE
of a subdivision of $G$. When considering a 2UTBE as a planar drawing, each
subdivision vertex of an edge $e$ can be regarded as a point where $e$ crosses
the spine, and therefore is also called a _spine crossing_ (see Fig. 1).
Further, each of the “pieces” of an edge $e$ defined by the subdivision
vertices is called a _sub-edge_ of $e$; specifically, the sub-edges that are
in the top page are called _top sub-edges_ and those that are in the bottom
page are called _bottom sub-edges_. We write (sub-)edge to mean an element
that is either an edge or a sub-edge. We assume that in a 2UTBE no spine
crossing has two incident sub-edges that are in the same page; if so, the two
sub-edges can be replaced by a single (sub-)edge (see Fig. 1). A 2UTBE is a
_single-top 2UTBE_ if each edge has at most one top sub-edge (and hence at
most two bottom sub-edges).

A set of points $S$ is an _upward one-sided convex (UOSC) point set_ if the
points of $S$ are in convex position and the lowest point of $S$ is adjacent
to the highest point of $S$ in the convex hull. See Fig. 9 for an
illustration. We denote by $CH(S)$ the convex hull of $S$. We always assume
that all the points of $S$ are to the left of the line passing through the
topmost and the bottommost point.

##  3 Conditions for the existence of a $1$-bend UPSE

We begin with a necessary condition for the existence of a $1$-bend UPSE.

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

Let $G=(V,E)$ be an upward planar graph. If $G$ admits a $1$-bend UPSE on an
UOSC point set, then $G$ admits a single-top 2UTBE.

###### Proof

Let $\Gamma$ be a $1$-bend UPSE of $G$ on an UOSC point set $S$. For each edge
$e$ of $\Gamma$, replace each intersection point between $e$ and $CH(S)$ that
is not an end-vertex of $e$, with a dummy vertex. We obtain a $1$-bend upward
planar drawing $\Gamma^{\prime}$ of a subdivision
$G^{\prime}=(V^{\prime},E^{\prime})$ of $G$, such that each edge is drawn
completely outside $CH(S)$ or completely inside $CH(S)$. Notice that an edge
of $\Gamma^{\prime}$ that is drawn completely outside $CH(S)$ has necessarily
at least one bend, as edges with no bends necessarily lie inside $CH(S)$.
Thus, an edge of $\Gamma$ can be split by its intersection points with $CH(S)$
in at most three “pieces”, at most one of which can be outside $CH(S)$.

We can define a 2UBE $\gamma^{\prime}$ of $G^{\prime}$ as follows. The total
order of $V^{\prime}$ coincides with the bottom to top order of the vertices
(real and dummy) in $\Gamma^{\prime}$; the edges that are drawn inside $CH(S)$
are assigned to the bottom page and those that are drawn outside $CH(S)$ are
assigned to the top page. Since $\Gamma^{\prime}$ is an upward drawing, the
total order of $V^{\prime}$ is a topological sorting. Further, in
$\gamma^{\prime}$, no two edges in the same page cross, as otherwise the same
edges would cross in $\Gamma^{\prime}$. Since $G^{\prime}$ is a subdivision of
$G$, $\gamma^{\prime}$ is a 2UTBE of $G$. Also, as observed above, each edge
$e$ of $G$ is split so that at most one “piece” is drawn outside $CH(S)$,
hence $e$ has at most one top sub-edge in $\gamma^{\prime}$.

Given a 1-bend UPSE $\Gamma$ on an UOSC point set $S$, we say that the 2UTBE
$\gamma$ that can be obtained as explained in the proof of Lemma 1 is
_induced_ by $\Gamma$.

We now give a sufficient condition for the existence of a $1$-bend UPSE. We
begin by introducing some additional definitions and technical lemmas. Let
$\gamma$ be a single-top 2UTBE of an upward planar graph $G$. A sub-edge
$(u,v)$ with $u\prec v$ _is nested inside_ another sub-edge $(w,z)$ with
$w\prec z$ if the two sub-edges are in the same page and $w\preceq u\prec
v\preceq z$. Notice that it cannot be that $w=u$ and $v=z$ at the same time.
An (sub-)edge $(w,z)$ with $w\prec z$ _covers_ a vertex $v$ if $w\prec v\prec
z$. Let $e_{1}$ and $e_{2}$ be two edges of $G$. Edges $e_{1}$ and $e_{2}$
form a _forbidden configuration_ in $\gamma$ if the following three conditions
hold simultaneously: (a) $e_{1}$ and $e_{2}$ both have a top sub-edge, one of
the top sub-edges is nested inside the other, and the two sub-edges can
possibly share a vertex; (b) $e_{1}$ and $e_{2}$ both have a bottom sub-edge,
one of the bottom sub-edges is nested inside the other, and the sub-edges do
not share a vertex; and (c) each bottom sub-edge covers at least one vertex
and each top sub-edge covers at least two vertices. We have four possible
forbidden configurations: _Type 1 forbidden configuration_ is such that the
top sub-edges do not share a vertex and the two bottom sub-edges precede the
two top sub-edges in the direction of the spine (see Fig. 2(a)); _Type 2
forbidden configuration_ is like the Type 1 forbidden configuration but with
the top edges that share a vertex (see Fig. 2(b)). _Type 3_ and _Type 4
forbidden configurations_ are like Type 1 and Type 2 respectively, but the top
sub-edges precede the bottom sub-edges (see Fig. 2(c) and 2(d)). We say that
the 7 (or 6) vertices necessary to have a forbidden configuration are _the
vertices that define_ the forbidden configuration. These are the 4 (or 3) end-
vertices of the two edges forming the forbidden configuration and the three
vertices that are covered by their sub-edges. A single-top 2UTBE is _nice_ if
it has no forbidden configuration.

(a) Type 1

(b) Type 2

(c) Type 3

(d) Type 4

Figure 2:  Forbidden configurations.

(a) Type 1

(b) Type 2

(c) Type 3

(d) Type 4

Figure 3:  Impossible point sets.

The next lemma shows that forbidden configurations are obstacles to the
existence of a 1-bend UPSE for specific set of points. We describe 4 types of
UOSC point sets, one for each type of forbidden configuration. See Fig. 3 Let
$p_{1},p_{2},p_{3},p_{4},p_{5},p_{6},p_{7}$ be a set $S$ of points ordered
from bottom to top. Denote by $C_{i}$, with $i\in\\{1,2\\}$ the cone defined
by the two half-lines starting at $p_{i}$ and passing through $p_{3}$ and
$p_{4}$, respectively. Also, denote by $H_{i}$, with $i\in\\{6,7\\}$ the half
plane above the straight line passing through $p_{i-1}$ and $p_{i}$. Finally,
denote by $T_{1}$ the portion of $C_{1}$ that does not intersect $H_{6}$ and
by $T_{2}$ the portion of $C_{2}$ that does not intersect $H_{7}$. We say that
$T_{1}$ and $T_{2}$ cross each other if every segment connecting $p_{1}$ to
the opposite side of $T_{1}$ crosses every segment that connects $p_{2}$ to
the opposite side of $T_{2}$. If $S$ is such that $T_{1}$ and $T_{2}$ cross,
we say that $S$ is a _Type 1 impossible point set_ (see Fig. 3(a)). A _Type 2
impossible point set_ is like a Type 1 impossible point set, but with $p_{6}$
and $p_{7}$ coincident – in this case the two half planes $H_{6}$ and $H_{7}$
are also coincident (see Fig. 3(b)). _Type 3_ and _Type 4 impossible points
sets_ are like Type 1 and Type 2 respectively, but mirrored vertically (see
Fig. 3(c) and 3(d)).

###### Lemma 2

If a single-top 2UTBE $\gamma$ contains a forbidden configuration of Type $i$,
with $i\in\\{1,2,3,4\\}$, then there does not exist a 1-bend UPSE whose
induced 2UTBE is $\gamma$ and such that the vertices that define the forbidden
configuration are mapped to an impossible point set of Type $i$.

###### Proof

Assume that $\gamma$ has a Type 1 forbidden configuration (the other cases are
analogous). Denote the two edges forming the forbidden configuration as
$e_{1}$ and $e_{2}$, with the top sub-edge of $e_{1}$ nested inside the top
sub-edge of $e_{2}$. Suppose that an UPSE exists whose induced 2UTBE is
$\gamma$ and such that the vertices of the forbidden configuration are mapped
to the points of a Type 1 impossible point set. Then both $e_{1}$ and $e_{2}$
have one bend; the bend of $e_{1}$ is a point of $C_{1}\cap H_{6}$, and the
one of $e_{2}$ is a point of $C_{2}\cap H_{7}$. This implies that the portion
of $e_{1}$ drawn inside $T_{1}$ crosses the portion of $e_{2}$ drawn inside
$T_{2}$ (see Fig. 2(a) and 3(a)).

In the rest of this section, we prove that if $G$ has a nice single-top 2UTBE
then it admits a 1-bend UPSE on every UOSC point set. Let $S$ be an UOSC point
set of size $n$. Let $\gamma$ be a 2UTBE of an $n$-vertex upward planar graph
$G$ and let $v_{1},v_{2},\dots,v_{n^{\prime}}$ be the sequence of vertices
along the spine obtained by replacing each spine crossing with a dummy vertex.
An _enrichment of $S$ consistent with $\gamma$_ is an UOSC point set
$S^{\prime}$ such that: (i) $S\subset S^{\prime}$; (ii)
$|S^{\prime}|=n^{\prime}$; and (iii) if we denote by
$p_{1},p_{2},\dots,p_{n^{\prime}}$ the points of $S^{\prime}$ in bottom-to-top
order, then $p_{i}$ is a dummy point if and only if $v_{i}$ is a dummy vertex.
See Fig. 4.

Let $\gamma$ be a single-top 2UTBE of an upward planar graph $G$, and let
$\gamma^{\prime}$ be the 2UBE obtained by replacing the spine crossings of
$\gamma$ with dummy vertices and let $\gamma^{\prime}_{top}$ be the 1-page
book embedding obtained by $\gamma^{\prime}$ considering only the top page; we
call $\gamma^{\prime}_{top}$ the _top-reduction_ of $\gamma$. See Fig. 4. Let
$S$ be an $n$-point one-sided convex point set and let $S^{\prime}=\langle
p_{1},p_{2},\dots,p_{n^{\prime}}\rangle$ be an enrichment of $S$ consistent
with $\gamma$. We assign to each dummy vertex $v_{i}$ in
$\gamma^{\prime}_{top}$ a slope $\sigma$, which has to be used to draw the
segment incident to the dummy vertex. If $v_{i}$ is adjacent to a vertex
$v_{j}$ (real or dummy) with $j>i$, then $\sigma$ is a slope of the II-IV
quadrant defined by the Cartesian axes, while if $v_{i}$ is adjacent to a
vertex $v_{j}$ (real or dummy) with $j<i$, then $\sigma$ is a slope of the
I-III quadrant. In either case the value of $\sigma$ must be smaller, in
absolute value, than the slope of any segment $\overline{p_{k}p_{k+1}}$ for
$k=i,i+1,\dots,j-1$ if $i<j$ or for $k=j,j+1,\dots,i-1$ if $i>j$. Such a
choice of slopes is called a _slope assignment_ for $\gamma^{\prime}_{top}$.
Let $e_{1}$ and $e_{2}$ be two sub-edges with at least one dummy end-vertex
each and such that $e_{2}$ is nested inside $e_{1}$. The slope assignment is
_good for $e_{1}$ and $e_{2}$_ if for any two slopes $\sigma_{1}$ assigned to
$e_{1}$ and $\sigma_{2}$ assigned to $e_{2}$ in the same quadrant we have
$|\sigma_{1}|<|\sigma_{2}|$. The slope assignment is _good_ if it is good for
every pair of nested sub-edges.

Figure 4:  (a) A single-top 2UTBE $\gamma$; (b) the top-reduction
$\gamma^{\prime}_{top}$ of $\gamma$; (c) an enrichment of an UOSC point set
$S$ (black squares) consistent with $\gamma$ with a good slope assignment. (d)
A $1$-bend UPSE of $\gamma^{\prime}_{top}$ on $S^{\prime}$ computed as in
Lemma 3.

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

Let $G$ be an $n$-vertex upward planar graph, let $S$ be an UOSC point set.
Let $\gamma$ be a single-top 2UTBE of $G$ and let $\gamma^{\prime}_{top}$ be
the top-reduction of $\gamma$. If a good slope assignment is given, then
$\gamma^{\prime}_{top}$ has a 1-bend UPSE on every enrichment $S^{\prime}$ of
$S$ consistent with $\gamma$ such that all the edges are drawn outside
$CH(S^{\prime})$ and the segment incident to each dummy vertex is drawn with
the assigned slope.

###### Proof

Let $v_{1},v_{2},\dots,v_{n^{\prime}}$ be the vertices in
$\gamma^{\prime}_{top}$ according to the spine order. Let $S^{\prime}=\langle
p_{1},p_{2},\dots,p_{n^{\prime}}\rangle$ be an enrichment of $S$ consistent
with $\gamma$. (See Fig. 4).

The edges are drawn according to an order defined by the nesting, i.e., an
edge is drawn only after that all edges nested inside it are already drawn.
Let $e=(v_{i},v_{j})$ be the current edge to be drawn and suppose that $i<j$,
i.e., that $v_{i}\prec v_{j}$. The edge $e$ is drawn as the union of two
segments: $s_{i}$ incident to $v_{i}$ and $s_{j}$ incident to $v_{j}$. The
segment $s_{i}$ is drawn in the II quadrant, while segment $s_{j}$ is drawn in
the III quadrant. This guarantees that $s_{i}$ and $s_{j}$ can meet at a bend
point. If $v_{i}$ (resp. $v_{j}$) is a dummy vertex, then $s_{i}$ (resp.
$s_{j}$) is drawn with the slope assigned to $v_{i}$ (resp. $v_{j}$). Notice
that the slope assigned to $v_{i}$ (resp. $v_{j}$) is a slope of the II-IV
quadrant (resp. I-III quadrant). If $v_{i}$ (resp. $v_{j}$) is a real vertex,
then $s_{i}$ (resp. $s_{j}$ ) is drawn with a slope $\sigma$ of the II-IV
quadrant (resp. I-III quadrant) and such that the value of $\sigma$ is
smaller, in absolute value, than the value of any other slope used in the
edges nested inside $(v_{i},v_{j})$ (which have already been drawn). If no
edge is nested inside $(v_{i},v_{j})$, then $|\sigma|$ has to be smaller than
the absolute value of the slope of any segment $\overline{p_{k}p_{k+1}}$, for
$k=i,i+1\dots,j-1$.

The slopes used to draw the edges are such that all the segments are drawn
outside $CH(S)$ except for an endpoint for each segment, which coincides with
a point of $S^{\prime}$. This is true because every segment $s$ of an edge is
drawn with a slope (assigned or chosen by the algorithm) that is smaller, in
absolute value, than the slope of any segment of $CH(S)$ that can potentially
intersect $s$. Moreover, the slopes of the two segments of an edge $e$ are
smaller, in absolute value, than the slopes of all the segments of the edges
nested inside $e$. This implies that there is no edge crossing.

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

Let $G$ be an $n$-vertex upward planar graph, let $\gamma$ be a single-top
2UTBE of $G$, and let $e$ be a top sub-edge that covers exactly one vertex and
that has no top sub-edge nested inside it. Let $\gamma^{\prime}$ be the 2UTBE
obtained from $\gamma$ by removing the edge $e^{\prime}$ containing the sub-
edge $e$. Let $\Gamma^{\prime}$ be a $1$-bend UPSE of
$G\setminus\\{e^{\prime}\\}$ on an UOSC point set $S$ whose induced 2UTBE is
$\gamma^{\prime}$. Then it is possible to construct a 1-bend UPSE of $G$ on
$S$ that has $\Gamma^{\prime}$ as a sub-drawing.

###### Proof

Let $v_{i}$ and $v_{j}$ be the two end-vertices of the edge $e^{\prime}$ and
suppose that $i<j$, i.e., that $v_{i}\prec v_{j}$. Let $v_{k}$ be the single
vertex covered by the top sub-edge $e$ of $e^{\prime}$; clearly, $i<k<j$,
i.e., $v_{i}\prec v_{k}\prec v_{j}$. There is no edge that crosses the
segments $\overline{v_{i}v_{k}}$ and $\overline{v_{k}v_{j}}$ (although one of
these segments can coincide with an edge) as otherwise there would be an edge
crossing $e^{\prime}$ in $\gamma$. Since no top sub-edge is nested inside $e$,
we can draw the edge $e^{\prime}$ by choosing a bend point slightly above
$v_{k}$ and connecting it with $v_{i}$ and $v_{j}$ (see Fig. 5).

Figure 5:  (a) A $1$-bend UPSE of the graph of Fig. 4 with one edge removed
(the two end-vertices of the removed edge are highlighted); the top sub-edge
of the removed edge covers only one vertex; (b) the addition of the missing
edge (close-up).

######  Lemma 5 ($\star$)

Let $G=(V,E)$ be an $n$-vertex upward planar graph. If $G$ admits a nice
single-top 2UTBE, then $G$ admits a $1$-bend UPSE on every UOSC point set $S$
of size $n$.

###### Proof

If $G$ admits a nice single-top 2UTBE $\gamma$, then we can compute a 1-bend
UPSE on every one-sided convex point set $S$ as follows. Let
$S^{\prime}=\langle p_{1},p_{2},\dots,p_{n^{\prime}}\rangle$ be an enrichment
of $S$ consistent with $\gamma$. We remove all edges that have a top sub-edge
covering only one vertex and nest no edges inside. If after such a removal,
some new edges with the same properties are created they are recursively
removed, until no more edge exists with the same properties. The reason we
remove these edges is to guarantee that, in the description that follows, we
can assume that if a pair of edges satisfies Condition (a) of the definition
of forbidden configuration, they also satisfy Condition (c), and therefore
they do not satisfy Condition (b). The removed edges will be reinserted at the
end in reverse order of removal using Lemma 4.

Let $\gamma^{\prime}$ be the single-top 2UTBE resulting from the edge removal
explained above and let $G^{\prime}$ be the corresponding graph. We now
compute a $1$-bend UPSE of $G^{\prime}$ on $S^{\prime}$. We first map each
vertex $v_{i}$ to the point $p_{i}$ ($i=1,2,\dots,n^{\prime}$). Notice that by
the choice of the additional points, the dummy vertices are mapped to the
dummy points. We then draw the (sub-)edges that are in the bottom page as a
straight-line segments inside the convex hull $CH(S^{\prime})$ of
$S^{\prime}$. Since the bottom-to-top order of the vertices along
$CH(S^{\prime})$ is the same as in $\gamma^{\prime}$, the (sub-)edges drawn
inside $CH(S^{\prime})$ do not cross each other.

Now, in order to draw the top (sub-)edges, we consider the top restriction of
$\gamma^{\prime}$, and define a slope assignment, assigning to each dummy
vertex $d$ the slope of the segment incident to $d$ that is in the bottom page
(drawing the segment incident to $d$ with this slope guarantee that no
additional bend is created at $d$). We now prove that this slope assignment is
good and thus by Lemma 3 all the top (sub-)edges can be drawn outside the
convex hull respecting the slope assignment, which guarantees that each edge
is drawn with one bend.

Let $e_{1}=(v_{i_{1}},v_{j_{1}})$, with $i_{1}<j_{1}$, and
$e_{2}=(v_{i_{2}},v_{j_{2}})$ with $i_{2}<j_{2}$ be two top sub-edges such
that $e_{2}$ is nested inside $e_{1}$, i.e., such that $v_{i_{1}}\preceq
v_{i_{2}}\prec v_{j_{2}}\preceq v_{j_{1}}$. Each sub-edge has one or two
assigned slopes depending on the number of dummy vertices. Consider any two
slopes, $\sigma_{1}$ assigned to an end-vertex of $e_{1}$ and $\sigma_{2}$
assigned to an end-vertex of $e_{2}$. In order to prove that the described
slope assignment is good we have to prove that either $\sigma_{1}$ and
$\sigma_{2}$ are in different quadrants, or they are in the same quadrant and
$|\sigma_{1}|<|\sigma_{2}|$. Thus, in the following, assume that $\sigma_{1}$
and $\sigma_{2}$ are in the same quadrant.

If $\sigma_{1}$ is assigned to $v_{i_{1}}$ and $\sigma_{2}$ is assigned to
$v_{j_{2}}$ or $\sigma_{1}$ is assigned to $v_{j_{1}}$ and $\sigma_{2}$ is
assigned to $v_{i_{2}}$, then they are in different quadrants. So, assume that
$\sigma_{1}$ is assigned to $v_{i_{1}}$ and $\sigma_{2}$ is assigned to
$v_{i_{2}}$ (the case when $\sigma_{1}$ is assigned to $v_{j_{1}}$ and
$\sigma_{2}$ is assigned to $v_{j_{2}}$ is symmetric). Consider the bottom
sub-edge $e^{\prime}_{1}=(v_{k_{1}},v_{i_{1}})$ that shares $v_{i_{1}}$ with
$e_{1}$ and the bottom sub-edge $e^{\prime}_{2}=(v_{k_{2}},v_{i_{2}})$ that
shares $v_{i_{2}}$ with $e_{2}$. By Condition (b) of the definition of
forbidden configuration, either $v_{k_{1}}=v_{k_{2}}$ or the bottom sub-edges
are not nested, i.e., the order of the vertices is $v_{k_{1}}\prec
v_{i_{1}}\prec v_{k_{2}}\prec v_{i_{2}}\prec v_{j_{2}}\preceq v_{j_{1}}$. In
the first case, the two segments that represent $e^{\prime}_{1}$ and
$e^{\prime}_{2}$ (and that define the slope assigned to $e_{1}$ and to
$e_{2}$) share an end-vertex and since $v_{i_{2}}$ follows $v_{i_{1}}$ the
slope of the segment $\overline{v_{k_{1}}v_{i_{1}}}$ is smaller, in absolute
value than the slope of $\overline{v_{k_{1}},v_{i_{2}}}$. In the second case,
the segment $\overline{v_{k_{2}},v_{i_{2}}}$ has both end-vertices after the
end-vertices of the segment $\overline{v_{k_{1}},v_{i_{1}}}$; thus from the
one-sided convexity of $S$ it follows that the slope of
$\overline{v_{k_{2}},v_{i_{2}}}$ is larger, in absolute value, than the slope
of $\overline{v_{k_{1}},v_{i_{1}}}$. This concludes the proof that the slope
assignment is good and therefore, by Lemma 3, that it is possible to compute a
1-bend PSE of $G^{\prime}$ on $S^{\prime}$.

It remains to re-insert all the edges removed at the beginning of the
algorithm, i.e., those that had a sub-edge covering a single vertex and did
not have an edge nested inside them. These edges will be re-inserted in the
reverse order of removal. As a consequence, each time we add one such edge $e$
we are in the hypothesis of Lemma 4 and it is possible to re-insert $e$. Once
all the edges of $G\setminus G^{\prime}$, are reinserted and the dummy
vertices and points are removed, the resulting drawing is a $1$-bend UPSE of
$G$ on $S$.

##  4 1-bend UPSE of $st$-outerplanar graphs

A graph is _outerplanar_ if it admits an _outerplanar drawing_ , i.e., a
planar drawing in which all vertices belong to the boundary of the outer face,
which defines an _outerplanar embedding_. Unless otherwise specified, we will
assume our graphs to have planar or outerplanar embeddings. An edge of an
embedded planar graph $G$ is _outer_ if it belongs to the outer face, and it
is _inner_ otherwise. The _weak dual_ $\overline{G}$ of $G$ is the graph
having a node for each inner face of $G$, and an edge between two nodes if and
only if the two corresponding faces share an edge. If $G$ is outerplanar, its
weak dual $\overline{G}$ is a tree. If $\overline{G}$ is a path, $G$ is an
_outerpath_. A _fan_ is an internally-triangulated outerpath whose inner edges
all share an end-vertex.

An _$st$ -digraph_ is a directed acyclic graph with a single source $s$ and a
single sink $t$; an _$st$ -outerplanar graph_ (resp.  _$st$ -outerpath_) is an
$st$-digraph whose underlying undirected graph is an outerplanar graph (resp.
an outerpath). An _$st$ -fan_ is an $st$-digraph whose underlying graph is a
fan and whose inner edges have $s$ as an end-vertex. An $st$-outerplanar graph
such that the edge $(s,t)$ exists is _one-sided_ if $(s,t)$ is an outer edge,
it is _two-sided_ if $(s,t)$ is an inner edge.

We recall a decomposition of $st$-outerpaths defined in [7]. The _extreme
faces_ of an $st$-outerpath $G$ are the two faces that correspond to the two
degree-one nodes of the weak dual $\overline{G}$. An $st$-outerpath $G$ is
_primary_ if and only if one of its extreme faces is incident to $s$ and the
other one to $t$. Observe that this definition is stronger than the one used
in [7], in the sense that a primary $st$-outerpath according to our definition
is a primary $st$-outerpath also according to the definition in [7] (but the
converse may not be true). Let $G$ be a primary $st$-outerpath. Consider a
subgraph $F$ of $G$ that is an $xy$-fan (for some vertices $x,y$ of $G$). Let
$\langle f_{1},\dots,f_{h}\rangle$ be the list of faces forming the path
$\overline{G}$ ordered from $s$ towards $t$. Note that the subgraph $F$ of $G$
is formed by a subset of faces that are consecutive in the path $\langle
f_{1},\dots,f_{h}\rangle$. Let $f_{i}$ be the face of $F$ with the highest
index, with $1\leq i\leq h$. We say that $F$ is _incrementally maximal_ if
$i=h$ or $F\cup f_{i+1}$ is not an $xy$-fan. For every face $f_{i}$ we denote
by $\textrm{mid}(f_{i})$ the unique vertex of $f_{i}$ with one incoming edge
and one outgoing edge in the boundary of $f_{i}$.

###### Definition 1

An _$st$ -fan decomposition_ of a primary $st$-outerpath $G$ is a sequence of
$s_{i}t_{i}$-fans $F_{i}\subseteq G$, with $i=1,\dots,k$, such that: (i)
$F_{i}$ is incrementally maximal for each $i=1,\dots,k$; (ii) for any $1\leq
i<j\leq k$, $F_{i}$ and $F_{j}$ do not share any edge if $j>i+1$, while
$F_{i}$ and $F_{i+1}$ share a single edge, which we denote by $e_{i}$; (iii)
$s_{1}=s$; (iv) the tail of $e_{i}$ is $s_{i+1}$ for each $i=1,\dots,k-1$; (v)
$e_{i}\neq(s_{i},t_{i})$ for each $i=1,\dots,k-1$; and (vi)
$\bigcup_{i=1}^{k}F_{i}=G$. Refer to Fig. 6.a-b.

######  Lemma 6 ([7])

Every primary $st$-outerpath $G$ admits an $st$-fan decomposition.

Let $G$ be an $st$-outerplanar graph and let $\overline{P}$ be a path in the
weak dual $\overline{G}$ of $G$ whose two endpoints are such that one
corresponds to a face containing $s$ and the other one to a face containing
$t$. Observe that the primal graph $G_{core}$ of $\overline{P}$ is a primary
$st$-outerpath by construction, we call it the _core_ of $G$. On the other
hand, if an outer edge $(u,v)$ of $G_{core}$ is not an outer edge of $G$, then
it corresponds to a separation pair in $G$. In particular, $(u,v)$ belongs to
$G_{core}$ and to another subgraph $A_{uv}$ of $G$ which is a one-sided
$uv$-outerplanar graph; we call $A_{uv}$ an _appendage_ of $G$ _attached_ to
$(u,v)$; refer to Fig. 6.c.

Figure 6: (a) An $st$-fan in the middle of the $st$-fan decomposition. (b) The
first and last $st$-fans of the $st$-fan decomposition. Since the outerpath is
primary, the last fan can always be chosen to be one-sided with edge
$(s_{k},t_{k})$ regarded as a possible attachment edge of an appendage (light
blue). (c) $G_{core}$ is blue and gray, while green subgraphs represent
appendages of $G_{core}$. (d) Illustration of Property 1.b.

###### Property 1

Let $G$ be an $st$-outerplanar graph and let $G_{core}$ be the core of $G$.
The following properties hold:

  * (a)

Every outer edge of $G_{core}$ is potentially an attachment edge of an
appendage.

  * (b)

Let $F_{1},\dots,F_{k}$ be an $st$-fan decomposition of $G_{core}$ and let $P$
be its dual path. Let $s_{i}$, $t_{i}$ denote the source and the sink of
$F_{i}$. The fans $F_{i-1}$ and $F_{i}$ share the edge $(s_{i},t_{i-1})$; See
Fig. 6.d (Stronger version of Lemma 3 in [7]).

  * (c)

Path $P$ enters $F_{i}$, $i=2,\dots,k$ through the edge $(s_{i},t_{i-1})$ and
leaves $F_{i}$, $i=1,\dots,k-1$ through the edge $(s_{i+1},t_{i})$.

  * (d)

Let $F_{i}$ be a two-sided $st$-outerpath and let $f_{1},\dots,f_{a}$ be the
faces of $F_{i}$ as visited by $P$. Faces $f_{1},\dots,f_{a-1}$, $a\geq 2$,
lie on one side of $(s_{i},t_{i})$ and only the face $f_{a}$ lies on the other
side of $(s_{i},t_{i})$. Refer to Fig. 6.a.

Property (a) holds by definition. If Properties (b) and (c) do not hold, then
$G_{core}$ has either more than one sink or more than one source. Finally,
assuming that Property (d) does not hold, implies that $G_{core}$ is not an
outerpath.

In this section we utilize a tool, called _Hamiltonian completion_ , that is
another way to look at 2UTBEs. An upward planar graph $G$ has a 2UBE if and
only if it is _subhamiltonian_ , i.e., it is a spanning subgraph of an upward
planar $st$-digraph $\tilde{G}$ that has a directed Hamiltonian $st$-path
[30]. More generally, there is an analogy between upward topological book
embeddings and a more general form of subhamiltonicity. Let $G$ be an upward
planar graph and $\tilde{G}=(V,\tilde{E})$ be an embedded $st$-digraph such
that: (1) $G=(V,E)$ is a spanning subgraph of $\tilde{G}$, (2) $\tilde{G}$ has
a directed Hamiltonian $st$-path $H$, and (3) each edge in $E$ is crossed by
at most one edge of $\tilde{E}\setminus E$. We say that $H$ is a
_subhamiltonian path_ of $G$ and $\tilde{G}$ is an _HP-completion_ of $G$. See
Fig. 7 for an example of subhamiltonian paths.

######  Lemma 7 ([30])

An upward planar graph has a 2UTBE with at most one spine-crossing per edge if
and only if it has an HP-completion. The order of the vertices along the spine
in the 2UTBE is the same as in the subhamiltonian path.

The subhamiltonian path crosses some edges of $G$ by splitting them into _sub-
edges_. We inherit the definition of nesting (sub-)edges from 2UTBE to HP-
completion. Thus, the (sub-)edges $(u,v)$, $(w,z)$ _nest_ in $\tilde{G}$ if in
the embedding of $\tilde{G}$ they are on the same side of the path $H$ and
$u\prec w\prec z\prec v$ or $w\prec u\prec v\prec z$. Since the order of the
vertices on the spine of the book and along the Hamiltonian path coincide, two
(sub-)edges nest in $\tilde{G}$ if and only if they nest in the corresponding
2UTBE. We now prove the key result of this section.

######  Lemma 8 ($\star$)

Every primary st-outerpath has an HP-completion without nesting sub-edges.

######  Proof (sketch)

Let $G$ be a primary $st$-outerpath and $F_{1},\dots,F_{k}$ be its $st$-fan
decomposition. Let $\overline{P}$ be the dual path of $G$. Let $G_{i}$ be the
subgraph of $G$ composed by $F_{1},\dots,F_{i}$, $i=1,\dots,k$, therefore
$G=G_{k}$. We construct the subhamiltonian path $H_{i}$ in $G_{i}$ by
induction on $i$, assuming the next invariants for $H_{i-1}$ in $G_{i-1}$:

  1. $\mathcal{I}1$

Subhamiltonian path $H_{i-1}$ in $G_{i-1}$ terminates with the edge
$(s_{i},t_{i-1})$.

  2. $\mathcal{I}2$

Path $H_{i-1}$ crosses the edge $(s_{i-1},t_{i-1})$ (in a point referred to as
$p_{i-1}$) if and only if $F_{i-1}$ is two-sided. No other edge of $F_{i-1}$
is crossed by $H_{i-1}$.

  3. $\mathcal{I}3$

$H_{i-1}$ does not create nesting sub-edges in $G_{i-1}$.

We show how to construct $H_{i}$ so to maintain the invariants. We have three
cases based on whether $F_{i-1}$ and $F_{i}$ are two-sided or not.

### Case 1:

both $F_{i-1}$ and $F_{i}$ are two-sided. Refer to Fig. 7.a. Consider the dual
path $\overline{P}$ in $F_{i}$ and let $f_{1},\dots,f_{a}$, be the faces of
$F_{i}$ as visited by $\overline{P}$. By Property 1(d), since $F_{i}$ is two-
sided, faces $f_{1},\dots,f_{a-1}$, $a\geq 2$, lie on one side of
$(s_{i},t_{i})$ and only the face $f_{a}$ lies on the other side of
$(s_{i},t_{i})$. Note that, by Properties 1(b) and 1(c), $F_{i-1}$ and $F_{i}$
share $(s_{i},t_{i-1})$ and $P$ enters $F_{i}$ through $(s_{i},t_{i-1})$; it
follows that $\textrm{mid}(f_{1})=t_{i-1}$. By induction hypothesis $H_{i-1}$
terminates at $(s_{i},t_{i-1})$. Therefore, we can set path $H_{i}$ to be
$H_{i-1}$ concatenated with
$\textrm{mid}(f_{1}),\dots,\textrm{mid}(f_{a}),t_{i}$. Note that
$\textrm{mid}(f_{a})=s_{i+1}$, thus Invariant $\mathcal{I}1$ holds. Also,
$H_{i}$ crosses $(s_{i},t_{i})$ and no other edge of $F_{i}$, hence Invariant
$\mathcal{I}2$ holds as well. Finally, concerning the only two edges of
$F_{i-1}$ and $F_{i}$ that are crossed by $H_{i}$, the order in which their
end-vertices $s_{i}$, $t_{i}$, $s_{i-1}$, and $t_{i-1}$ and their crossing
points $p_{i-1}$ and $p_{i}$ are visited is
$s_{i-1},p_{i-1},s_{i},t_{i-1},p_{i},t_{i}$, which implies that their sub-
edges do not nest. No other sub-edge is created by $H_{i}$, thus
$\mathcal{I}3$ holds.

### Case 2:

$F_{i-1}$ is one-sided and $F_{i}$ is two-sided. Again, by Property 1(c),
$H_{i-1}$ ends with $(s_{i},t_{i-1})$. Consider the dual path $\overline{P}$
in $F_{i}$ and let $f_{1},\dots,f_{a}$, be the faces of $F_{i}$ as visited by
$P$. By Property 1(d), since $F_{i}$ is a two-sided, faces
$f_{1},\dots,f_{a-1}$, $a\geq 2$ lie on one side of $(s_{i},t_{i})$, and only
the face $f_{a}$ lies on the other side of $(s_{i},t_{i})$. Faces
$f_{1},\dots,f_{a-1}$ lie on the same side of $(s_{i},t_{i})$ where
$(s_{i},t_{i-1})$ lies, as $\overline{P}$ enters $F_{i}$ through
$(s_{i},t_{i-1})$. Therefore, we can concatenate $H_{i-1}$ with
$\textrm{mid}(f_{1})=t_{i-1},\dots,\textrm{mid}(f_{a}),t_{i}$; see Fig. 6.b.
Also in this case $\textrm{mid}(f_{a})={s_{i+1}}$ and therefore Invariant
$\mathcal{I}1$ holds. Further, path $H_{i}$ crosses $(s_{i},t_{i})$ and
Invariant $\mathcal{I}2$ also holds. Since $H_{i-1}$ has no nesting sub-edges,
and any sub-edge in $G_{i-1}$ ends before the sub-edge of $F_{i}$ starts
(since $t_{i-2}$ is connected by a directed path to $s_{i}$) we have that
$H_{i}$ does not have nesting sub-edges and thus also $\mathcal{I}3$ holds.

### Case 3:

$F_{i}$ is one-sided. We distinguish two sub-cases depending on whether
$t_{i-1}$ coincides with $t_{i}$ or not.

### Case 3.a:

$t_{i-1}\neq t_{i}$ (refer to Fig. 6.c-d). Since $H_{i-1}$ ends with
$(s_{i,t_{i-1}})$, we can concatenate $H_{i-1}$ with
$\textrm{mid}(f_{1})=t_{i-1},\dots,\textrm{mid}(f_{a}),t_{i}$. Also in these
cases $\textrm{mid}(f_{a})=s_{i+1}$ and Invariant $\mathcal{I}1$ holds. Since
$F_{i}$ is one-sided, Invariant $\mathcal{I}2$ trivially holds. Finally, since
$F_{i}$ is one-sided, all the vertices
$\textrm{mid}(f_{1})=t_{i-1},\dots,\textrm{mid}(f_{a}),t_{i}$ lie on the same
side as $(s_{i},t_{i-1})$ and therefore path $H_{i}$ does not cross any edge
of $F_{i}$. This, and the induction hypothesis $\mathcal{I}3$ imply that
$H_{i}$ does not have nesting sub-edges.

### Case 3.b:

$t_{i-1}=t_{i}$ (refer to Fig. 6.e).In this case $a=1$, i.e., $F_{i}$ consists
of a single triangle $s_{i},\textrm{mid}(f_{1}),t_{i}$. We remove the edge
$(s_{i},t_{i-1})$ from $H_{i-1}$ and extends the resulting path with the two
edges $(s_{i},\textrm{mid}(f_{1}))$ and $(\textrm{mid}(f_{1}),t_{i})$.
Invariant $\mathcal{I}1$ holds by construction; Invariant $\mathcal{I}2$
trivially holds because $F_{i}$ is one-sided; finally, Invariant
$\mathcal{I}3$ holds because it held for $H_{i-1}$ and the extension to
$H_{i}$ cannot create any nesting.

Figure 7: Proof of Lemma 8: (a) Case 1. (b-d) Case 2, 3.a, and 3.b. The
subhamiltonian path $H_{i}$ is drawn in dark red.

###### Lemma 9

Every st-outerplanar graph has an HP-completion without nesting sub-edges.

###### Proof

Let $G$ be an $st$-outerplanar graph and let $G_{core}$ be the core of $G$. By
Lemma 8, $G_{core}$ has an HP-completion with subhamiltonian path $H^{\prime}$
that does not create nesting sub-edges. By Property 1(a), every outer edge of
$G_{core}$ is potentially an attachment edge of an appendage of $G$. We expand
the subhamiltonian path $H^{\prime}$ of $G_{core}$ to a subhamiltonian path
$H$ in $G$ as follows, refer to Fig. 8. Let $A$ be an appendage of $P$
attached to an edge $e$ and let $f$ be the internal face of $G_{core}$
incident to the edge $e$. We flip $A$ to lie inside $f$. We visit all the
vertices of $A$ that are not the source or the sink of $A$ either immediately
after $H^{\prime}$ visits the source of $A$ (blue appendage in Fig. 8.c) or
immediately before it visits the sink of $A$ (pink appendage in Fig. 8.c), or
both things at the same time (green appendages in Fig. 8.c). After this
procedure the edges crossed by $H$ are exactly the edges of $G_{core}$ crossed
by $H^{\prime}$, i.e., no new sub-edge is created. Further, the vertices of
$G_{core}$ are visited in the same order by $H$ and by $H^{\prime}$. Hence,
since $H^{\prime}$ did not create nesting sub-edges in $G_{core}$, so does $H$
in $G$.

Figure 8: Augmenting the subhamitonian path to visit appendages.

By Lemmas 9 and 7 every $st$-outerplanar graph has a nice 2UTBE with at most
one spine-crossing per edge. By Lemma 5 we have the following.

###### Theorem 4.1

Every $st$-outerplanar graph admits a $1$-bend UPSE on every UOSC point set.

##  5 1-bend UPSE are not always possible

In this section we describe a $2$-outerplanar $st$-digraph $G$ and an UOSC
point set $S$ such that $G$ does not admit a $1$-bend UPSE on $S$. An
$st$-digraph is $2$-outerplanar if removing all vertices of the outer face
yields an outerplanar digraph. The point set $S$ used in the proof of Lemma 10
is constructed in such a way that, assuming the existence of a 1-bend UPSE
$\Gamma$ on $S$, no matter what is the single-top 2UTBE induced by $\Gamma$,
there is always a forbidden configuration that is mapped to an impossible
point set, thus implying the existence of a crossing. It is possible to define
many point sets that have this property. The one shown in Fig. 9 has points
with the following exact coordinates:

$\displaystyle p1$ $\displaystyle=$ $\displaystyle(93,0),$ $\displaystyle p2$
$\displaystyle=$ $\displaystyle(79,2),$ $\displaystyle p3$ $\displaystyle=$
$\displaystyle(73,4),$ $\displaystyle p4$ $\displaystyle=$
$\displaystyle(16,43),$ $\displaystyle p5$ $\displaystyle=$
$\displaystyle(8,49),$ $\displaystyle p6$ $\displaystyle=$
$\displaystyle(4,53),$ $\displaystyle p7$ $\displaystyle=$
$\displaystyle(2,56),$ $\displaystyle p8$ $\displaystyle=$
$\displaystyle(1,59),$ $\displaystyle p9$ $\displaystyle=$
$\displaystyle(0,63),$ $\displaystyle p10$ $\displaystyle=$
$\displaystyle(0,67),$ $\displaystyle p11$ $\displaystyle=$
$\displaystyle(1,71),$ $\displaystyle p12$ $\displaystyle=$
$\displaystyle(2,74),$ $\displaystyle p13$ $\displaystyle=$
$\displaystyle(4,77),$ $\displaystyle p14$ $\displaystyle=$
$\displaystyle(8,81),$ $\displaystyle p15$ $\displaystyle=$
$\displaystyle(16,87),$ $\displaystyle p16$ $\displaystyle=$
$\displaystyle(73,126),$ $\displaystyle p17$ $\displaystyle=$
$\displaystyle(79,128),$ $\displaystyle p18$ $\displaystyle=$
$\displaystyle(93,130).$

Figure 9: (a) An $st$-digraph $G$ and (b) an UOSC point set $S$ for the proof
of Lemma 10

######  Lemma 10 ($\star$)

There exists a $2$-outerplanar $st$-digraph $G$ and an UOSC point set $S$ such
that $G$ does not admit a $1$-bend UPSE on $S$.

###### Proof

Let $G$ be the $st$-digraph of Fig. 9 and let $S$ be the point set of Fig. 9
By Lemma 1, if $G$ has a 1-bend UPSE $\Gamma$ on $S$, then $\Gamma$ induces a
single-top 2UTBE. We show that every single-top 2UTBE $\gamma$ of $G$ has a
forbidden configuration of Type $i$, for some $i\in\\{1,2,3,4\\}$, that is
necessarily mapped to a Type $i$ impossible point subset of $S$. By Lemma 2 a
1-bend UPSE cannot exist. Let $p_{1},p_{2},\dots,p_{18}$ be the points of $S$
in bottom-to-top order. Let $\pi_{l}$ be the path from $u$ to $v$ to the left
of $(u,v)$ (red in Fig. 9) and let $\pi_{r}$ be the path from $u$ to $v$ to
the right of $(u,v)$ (blue in Fig. 9). The edge $(u,v)$ (yellow in Fig. 9) has
vertices on both sides. Thus, in every 2UTBE it crosses the spine either once
or twice and the vertices of $\pi_{l}$ must appear along the spine in the
order they appear along $\pi_{l}$; the same holds for $\pi_{r}$. We have
different cases. In each case we denote by $v_{1},v_{2},\dots,v_{n}$ the
sequence of vertices along the spine (thus vertex $v_{i}$ is mapped to point
$p_{i}$). In all cases $u$ is mapped to $p_{2}$ and $v$ is mapped to $p_{17}$.

Figure 10: Case 1 of Theorem 5.1.

Figure 11: Case 2.A of Theorem 5.1.

Case 1: Edge $(u,v)$ crosses the spine once (see Fig. 10 and 10). The first
sub-edge of $(u,v)$ is either a bottom or a top sub-edge. Int the first (resp.
second) case the vertex $w$ coincides with $v_{6}$ (resp. $v_{1}3$) and the
edges $(w,v)$ and $(u,v)$ form a Type 2 (resp. a Type 4) forbidden
configuration with the spine crossings between $v_{9}$ and $v_{10}$. Since,
$p_{2},p_{6},p_{9},p_{10},p_{16},p_{17}$ (resp.
$p_{2},p_{3},p_{9},p_{10},p_{13},p_{17}$) form a Type 2 (resp. a Type 4)
impossible point set (see Fig. 10 and 10), by Lemma 2 a 1-bend UPSE cannot
exist in this case.

Case 2: Edge $(u,v)$ crosses the spine twice. In this case $(u,v)$ consists of
three sub-edges $(u,d_{1})$, $(d_{1},d_{2})$, and $(d_{2},v)$, where $d_{1}$
and $d_{2}$ are spine crossings. Only $(d_{1},d_{2})$ is a top sub-edge. Thus,
the vertices of $\pi_{l}$ have to be distributed in the two intervals defined
by $(u,d_{1})$ and $(d_{2},v)$. We distinguish six sub-cases (five are
omitted) depending on the distribution of the vertices of $\pi_{l}$.

Case 2.A: $w$ is between $u$ and $d_{1}$ with a single vertex of $\pi_{l}$
between $d_{2}$ and $v$ (see Fig. 11). In this case $w$ coincides with $v_{6}$
and both $(w,v)$ and $(u,v)$ cross the spine between $v_{8}$ and $v_{9}$ and
between $v_{15}$ and $v_{16}$. The edges $(w,v)$ and $(u,v)$ form a Type 2
forbidden configuration. Since $p_{2},p_{6},p_{8},p_{9},p_{15},p_{17}$ form a
Type 2 impossible point set (see Fig. 11), by Lemma 2 a 1-bend UPSE cannot
exist.

Case 2.B: Vertex $w$ is between $u$ and $d_{1}$ and there are two vertices of
$\pi_{l}$ between $d_{2}$ and $v$ (see Fig. 12). In this case $w$ coincides
with $v_{6}$ and both edges $(w,v)$ and $(u,v)$ cross the spine once between
$v_{7}$ and $v_{8}$ and another time between $v_{14}$ and $v_{15}$. Also in
this case the edges $(w,v)$ and $(u,v)$ form a Type 2 forbidden configuration.
Since $p_{2},p_{6},p_{7},p_{8},p_{14},p_{17}$ form a Type 2 impossible point
set (see Fig. 12), by Lemma 2 a 1-bend UPSE cannot exist in this case.

Figure 12: Case 2.B of Theorem 5.1.

Case 2.C: Vertex $w$ is between $u$ and $d_{1}$ and there are three vertices
of $\pi_{l}$ between $d_{2}$ and $v$ (see Fig. 13). In this case $w$ coincides
with $v_{6}$ and the vertex $z$ coincides with $v_{15}$. Edges $(w,v)$ and
$(w,z)$ form a Type 4 forbidden configuration with spine crossings between
$v_{13}$ and $v_{14}$. Since $p_{6},p_{1}3,p_{14},p_{15},p_{17}$ form a Type 4
impossible point set (see Fig. 13), by Lemma 2 a 1-bend UPSE cannot exist in
this case.

Figure 13: Case 2.C of Theorem 5.1.

Case 2.D: vertex $w$ is between $d_{2}$ and $v$ and there is only one vertex
of $\pi_{l}$ between $u$ and $d_{1}$. The proof is symmetric to the Case 2.A
(see Fig. 14 and 14).

Case 2.E: vertex $w$ is between $d_{2}$ and $v$ and there are two vertices of
$\pi_{l}$ between $u$ and $d_{1}$. The proof is symmetric to the Case 2.B (see
Fig. 14 and 14).

Case 2.F: vertex $w$ is between $d_{2}$ and $v$ and there are three vertices
of $\pi_{l}$ between $u$ and $d_{1}$. The proof is symmetric to the Case 2.C
(see Fig. 14 and 14).

Figure 14: Case 2.D–2.F of Theorem 5.1.

The following theorem is easily derived from Lemma 10 by suitably adding, for
every $n\geq 18$, $n-18$ vertices to $G$ and $n-18$ points to $S$.

######  Theorem 5.1 ()

For every $n\geq 18$ there exists an $n$-vertex $2$-outerplanar $st$-digraph
$G$ and an UOSC point set $S$ such that $G$ does not admit a $1$-bend UPSE on
$S$.

###### Proof

For every $n>18$ we can transform the $st$-digraph $G$ of Lemma 10 to an
$st$-digraph $G^{\prime}$ with $n$ vertices as follows. We add to $G$ a
directed path $s_{0}s_{1}\dots s_{n^{\prime}+1}$, with $n^{\prime}=n-18$, so
that $s_{n^{\prime}+1}$ coincides with the single source $s$ of $G$; we then
connect each $s_{i}$ to the vertices $u$ and $t$ of $G$, for
$i=1,2,n^{\prime}$. The resulting digraph is an $st$-digraph. We also
transform the point set $S$ into a point set $S^{\prime}$, by adding
$n^{\prime}$ points that form a one-sided convex point set together with $S$
and such that the added points are the lowest of $S^{\prime}$. It is easy to
see that if $G^{\prime}$ admits a $1$-bend UPSE of $S^{\prime}$ then $G$
admits a $1$-bend UPSE on $S$.

##  6 Open problems

Various questions remain open related to Problem 1 and 2 of Section 1. Among
them:

  1. 1.

Investigate the non-upward version of Problem 1. We observe that the graph of
Theorem 5.1 is not a counterexample for this problem as it admits a (non-
upward) PSE on the set of points $S$ of Theorem 5.1 (see Fig. 15).

  2. 2.

Study Problem 2. In particular, it would be nice to find a characterization of
the digraphs that admit a $1$-bend UPSE on every UOSC point set.

Figure 15: A (non-upward) PSE of the graph of Fig. 9 on the point set of Fig.
9.

## References

  * [1] Angelini, P., Eppstein, D., Frati, F., Kaufmann, M., Lazard, S., Mchedlidze, T., Teillaud, M., Wolff, A.: Universal point sets for drawing planar graphs with circular arcs. J. Graph Algorithms Appl. 18(3), 313–324 (2014)
  * [2] Angelini, P., Frati, F., Geyer, M., Kaufmann, M., Mchedlidze, T., Symvonis, A.: Upward geometric graph embeddings into point sets. In: GD 2010. LNCS, vol. 6502, pp. 25–37. Springer (2010)
  * [3] Arseneva, E., Cano, P., Kleist, L., Mchedlidze, T., Mehrabi, S., Parada, I., Valtr, P.: Upward point set embeddings of paths and trees. In: WALCOM 2021. LNCS, vol. 12635, pp. 234–246. Springer (2021)
  * [4] Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. Theoretical Computer Science 408(2-3), 129–142 (2008)
  * [5] Bekos, M.A., Da Lozzo, G., Frati, F., Gronemann, M., Mchedlidze, T., Raftopoulou, C.N.: Recognizing dags with page-number 2 is NP-complete. Theor. Comput. Sci. 946, 113689 (2023)
  * [6] Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Comb. Theory, Ser. B 27(3), 320–331 (1979)
  * [7] Bhore, S., Da Lozzo, G., Montecchiani, F., Nöllenburg, M.: On the upward book thickness problem: Combinatorial and complexity results. Eur. J. Comb. 110, 103662 (2023)
  * [8] Binucci, C., Di Giacomo, E., Didimo, W., Estrella-Balderrama, A., Frati, F., Kobourov, S.G., Liotta, G.: Upward straight-line embeddings of directed graphs into point sets. Comput. Geom. 43(2), 219–232 (2010)
  * [9] Bose, P.: On embedding an outer-planar graph on a point set. Computational Geometry: Theory and Applications 23, 303–312 (2002)
  * [10] Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications 2(1), 1–15 (1997)
  * [11] Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. Journal of Graph Algorithms and Applications 10(2), 353–363 (2006)
  * [12] Chowdhury, M.E., Rahman, M.S.: Orthogonal point-set embeddings of 3-connected and 4-connected planar graphs. In: ICCIT 2011. pp. 327–332 (2011)
  * [13] Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Wismath, S.K.: Constrained point-set embeddability of planar graphs. IJCGA 20(5), 577–600 (2010)
  * [14] Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Book embeddability of series-parallel digraphs. Algorithmica 45(4), 531–547 (2006)
  * [15] Di Giacomo, E., Gasieniec, L., Liotta, G., Navarra, A.: On the curve complexity of 3-colored point-set embeddings. Theor. Comput. Sci. 846, 114–140 (2020)
  * [16] Di Giacomo, E., Liotta, G., Trotta, F.: Drawing Colored Graphs with Constrained Vertex Positions and Few Bends per Edge. Algorithmica 57(4), 796–818 (2010)
  * [17] Dujmović, V., Evans, W.S., Lazard, S., Lenhart, W.J., Liotta, G., Rappaport, D., Wismath, S.K.: On point-sets that support planar graphs. Comput. Geom. 46(1), 29–50 (2013)
  * [18] Durocher, S., Mondal, D.: Plane 3-trees: Embeddability and approximation. SIAM J. Discret. Math. 29(1), 405–420 (2015)
  * [19] Everett, H., Lazard, S., Liotta, G., Wismath, S.K.: Universal sets of _n_ points for one-bend drawings of planar graphs with _n_ vertices. Discret. Comput. Geom. 43(2), 272–288 (2010)
  * [20] Fulek, R., Tóth, C.D.: Universal point sets for planar three-trees. J. Discrete Algorithms 30, 101–112 (2015)
  * [21] Giordano, F., Liotta, G., Mchedlidze, T., Symvonis, A., Whitesides, S.: Computing upward topological book embeddings of upward planar digraphs. J. Discrete Algorithms 30, 45–69 (2015)
  * [22] Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified points. Amer. Math. Monthly 98(2), 165–166 (1991)
  * [23] Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of directed acyclic graphs: Part II. SIAM J. Comput. 28(5), 1588–1626 (1999)
  * [24] Kaufmann, M.: On point set embeddings for k-planar graphs with few bends per edge. In: SOFSEM 2019. LNCS, vol. 11376, pp. 260–271. Springer (2019)
  * [25] Kaufmann, M., Mchedlidze, T., Symvonis, A.: On upward point set embeddability. Comput. Geom. 46(6), 774–804 (2013)
  * [26] Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications 6(1), 115–129 (2002)
  * [27] Löffler, M., Tóth, C.D.: Linear-size universal point sets for one-bend drawings. In: GD 2015. LNCS, vol. 9411, pp. 423–429. Springer (2015)
  * [28] Mchedlidze, T.: Upward planar embedding of an n-vertex oriented path on $O(n^{2})$ points. Comput. Geom. 46(8), 1003–1008 (2013)
  * [29] Mchedlidze, T., Symvonis, A.: Crossing-free acyclic hamiltonian path completion for planar _st_ -digraphs. In: ISAAC 2009. LNCS, vol. 5878, pp. 882–891. Springer (2009)
  * [30] Mchedlidze, T., Symvonis, A.: Crossing-optimal acyclic hamiltonian path completion and its application to upward topological book embeddings. In: WALCOM 2009. LNCS, vol. 5431, pp. 250–261. Springer (2009)
  * [31] Pach, J., Wenger, R.: Embedding Planar Graphs at Fixed Vertex Locations. Graphs and Combinatorics 17(4), 717–728 (2001)