11institutetext:  Università degli Studi di Perugia, Italy
11email:
<EMAIL_ADDRESS>
# Quasi-upward Planar Drawings
with Minimum Curve Complexity††thanks: This work is partially supported by:
$(i)$ MIUR, grant 20174LF3T8 “AHeAD: efficient Algorithms for HArnessing
networked Data”, $(ii)$ Dipartimento di Ingegneria - Università degli Studi di
Perugia, grants RICBA19FM: “Modelli, algoritmi e sistemi per la
visualizzazione di grafi e reti” and RICBA20EDG: “Algoritmi e modelli per la
rappresentazione visuale di reti”.

Carla Binucci  (🖂) Emilio Di Giacomo
Giuseppe Liotta  Alessandra Tappini

###### Abstract

This paper studies the problem of computing quasi-upward planar drawings of
bimodal plane digraphs with minimum curve complexity, i.e., drawings such that
the maximum number of bends per edge is minimized. We prove that every bimodal
plane digraph admits a quasi-upward planar drawing with curve complexity two,
which is worst-case optimal. We also show that the problem of minimizing the
curve complexity in a quasi-upward planar drawing can be modeled as a min-cost
flow problem on a unit-capacity planar flow network. This gives rise to an
$\tilde{O}(m^{\frac{4}{3}})$-time algorithm that computes a quasi-upward
planar drawing with minimum curve complexity; in addition, the drawing has the
minimum number of bends when no edge can be bent more than twice. For a
contrast, we show bimodal planar digraphs whose bend-minimum quasi-upward
planar drawings require linear curve complexity even in the variable embedding
setting.

##  1 Introduction

Let $G$ be a _plane digraph_ , i.e., a directed graph with a given planar
embedding. A vertex $v$ of $G$ is _bimodal_ if the circular order of the edges
around $v$ can be partitioned into two (possibly empty) sets of consecutive
edges, one consisting of the incoming edges and the other one consisting of
the outgoing edges. If every vertex of $G$ is bimodal, $G$ is a _bimodal plane
digraph_. See for example Fig. 1.

A planar drawing of a bimodal plane digraph $G$ is _upward planar_ if all the
edges are represented by curves monotonically increasing in the vertical
direction. A digraph that admits an upward planar drawing is _upward planar_.
Having a bimodal embedding is a necessary but not sufficient condition for a
digraph to be upward planar [12]. For example, the (embedded) digraph in Fig.
1 is not upward planar.

Garg and Tamassia [21] proved that testing a bimodal digraph for upward
planarity is NP-hard in the variable embedding setting, i.e., when all
possible bimodal planar embeddings must be checked. In this setting, an
$O(n^{4})$-time algorithm exists for series-parallel digraphs [18], where $n$
is the number of vertices. FPT solutions, SAT formulations, and branch-and-
bound approaches have also been proposed for general digraphs (see, e.g., [3,
10, 18, 23]). On the other hand, upward planarity testing can be solved in
polynomial time in the fixed embedding setting, i.e., when the input is a
bimodal plane digraph $G$ and the algorithm tests whether $G$ admits an upward
planar drawing that preserves the given bimodal embedding [4]. See also [17]
for a survey on upward planarity.

Figure 1: (a) A bimodal plane digraph $G$. (b) A quasi-upward planar drawing
of $G$. (c) The same drawing with poly-line edges.

Motivated by the observation that only restricted families of bimodal digraphs
are upward planar, Bertolazzi et al. introduced quasi-upward planar drawings
[3]. A drawing $\Gamma$ of a digraph $G$ is _quasi-upward planar_ if it has no
edge crossings and for each vertex $v$ there exists a sufficiently small disk
$R$ of the plane, properly containing $v$, such that, in the intersection of
$R$ with $\Gamma$, the horizontal line through $v$ separates the incoming
edges (below the line) from the outgoing edges (above the line); see Fig. 1.
Intuitively, all the incoming edges enter $v$ from “below” and all the
outgoing edges leave $v$ from “above”. A digraph that admits a quasi-upward
planar drawing is _quasi-upward planar_. An edge of a quasi-upward planar
drawing that is not upward has at least one horizontal tangent. Each point of
horizontal tangency is called a _bend_ (see Fig. 1). This term is justified by
the fact that an edge with $b$ points of horizontal tangency can be
represented as a poly-line with $b$ bends (substituting each point of tangency
with a vertex $v$ and suitable orienting the edges incident to $v$, we obtain
an upward planar digraph which always has a straight-line upward planar
drawing [12]); see Fig. 1.

Bertolazzi et al. [3] prove that, different from upward planarity, having a
planar bimodal embedding is necessary and sufficient for a digraph to be
quasi-upward planar. They also study the problem of computing quasi-upward
planar drawings with the minimum number of bends and use a suitable flow
network to solve it in ${\tilde{O}}(n^{2})$-time in the fixed embedding
setting. They also describe a branch-and-bound algorithm in the variable
embedding setting. A list of papers about quasi-upward planarity also includes
[7, 8, 9].

Our contribution. In this paper we study the problem of computing quasi-upward
planar drawings with minimum curve complexity of bimodal plane digraphs
possibly having multiple edges. The _curve complexity_ is the maximum number
of bends along any edge of the drawing. We recall that minimizing the curve
complexity is a classical subject of investigation in Graph Drawing (see,
e.g., [2, 5, 7, 11, 14, 15, 16, 24, 26, 27]). Our results can be summarized as
follows.

  * •

In Section 3 we prove that every bimodal plane digraph admits an embedding-
preserving quasi-upward planar drawing with curve complexity two. This is
worst-case optimal, since the number of bends per edge in a quasi-upward
planar drawing is an even number and not all bimodal plane digraphs are upward
planar [12]. This result is the counterpart in the quasi-upward planar setting
of a well-known result by Biedl and Kant who prove, in the orthogonal setting,
that every plane graph of degree at most four admits an orthogonal drawing
with curve complexity two [5].

  * •

In Section 4 we study the problem of minimizing the curve complexity in a
quasi-upward planar drawing. This problem can be modeled as a min-cost flow
problem on a unit-capacity planar flow network. By exploiting a result of
Karczmarz and Sankowski [25] we obtain an algorithm to compute embedding-
preserving quasi-upward planar drawings that minimize the curve complexity and
that have the minimum number of bends when no edge can be bent more than twice
that runs in ${\tilde{O}}(m^{\frac{4}{3}})$ time, where $m$ is the number of
edges of the input digraph. We recall that the problem of computing planar
drawings that minimize the number of bends while keeping the curve complexity
bounded by a constant has already been studied, for example in the context of
orthogonal representations (see, e.g., [19, 20, 28]).

  * •

A quasi-upward planar drawing with minimum curve complexity may have linearly
many bends in total. Thus, a natural question to ask is whether these many
bends are sometimes necessary if we just minimize the number of bends
independent of the curve complexity and, if so, what the curve complexity may
be. In Section 5 we prove that for every $n\geq 39$ there exists a planar
bimodal digraph with $n$ vertices whose bend-minimum quasi-upward planar
drawings have at least $cn$ bends on a single edge, for a constant $c>0$. We
show that this bound holds even in the variable embedding setting. This result
can be regarded as the counterpart in the quasi-upward planar setting of a
result by Tamassia et al. [29] showing a similar lower bound on the curve
complexity of bend-minimum planar orthogonal representations.

Preliminaries are in Section 2, while Section 6 lists some open problems.
Proofs marked with ($\star$) are omitted or sketched and can be found in the
appendix.

##  2 Preliminaries

We consider multi-digraphs, that are directed graphs which can have multiple
edges. For simplicity we shall call them _digraphs_. We also assume the
digraphs to be connected; indeed a digraph $G$ has a quasi-upward drawing if
and only if each connected component of $G$ has a quasi-upward drawing. A
vertex of a digraph $G$ without incoming (outgoing) edges is a _source_
(_sink_) of $G$. A vertex that is not a source nor a sink is an _internal
vertex_.

A _drawing_ $\Gamma$ of a digraph $G=(V,E)$ is a mapping of the vertices of
$V$ to points of the plane, and of the edges in $E$ to Jordan arcs connecting
their corresponding endpoints but not passing through any other vertex.
Drawing $\Gamma$ is _planar_ if any two edges can only meet at common
endpoints. A digraph is _planar_ if it admits a planar drawing. A planar
drawing of a planar digraph $G$ subdivides the plane into topologically
connected regions, called _faces_. The infinite region is the _external face_.
A _planar embedding_ $\mathcal{E}$ of $G$ is an equivalence class of planar
drawings that define the same set of faces and have the same external face. A
planar embedding of a connected digraph can be uniquely identified by the
clockwise circular order of the edges around each vertex and by the external
face. A _plane digraph_ $G$ is a planar digraph with a given planar embedding.
The number of vertices encountered in a closed walk along the boundary of a
face $f$ of $G$ is the _degree_ of $f$, denoted as $\delta(f)$. If $G$ is not
biconnected, a vertex may be encountered more than once, thus contributing
more than once to the degree of the face. The _dual digraph_ of $G$ is a plane
digraph with a vertex for each face of $G$ and an edge $e^{\prime}$ between
two faces for each edge $e$ of $G$ shared by the two faces. The edge
$e^{\prime}$ is oriented from the face to the left of $e$ to the face to the
right of $e$.

##  3 Subdivisions of Bimodal Plane Digraphs

In this section we show how to suitably subdivide the edges of a bimodal plane
digraph so to obtain an upward plane digraph. We start by recalling the
notions of large angles and upward consistent assignments [4].

Bimodality and upward consistent assignments. Let $G$ be a bimodal plane
digraph. Let $f$ be a face of $G$, let $e_{1}$ and $e_{2}$ be two consecutive
edges encountered in this order when walking counterclockwise along the
boundary of $f$, and let $v$ be the vertex shared by $e_{1}$ and $e_{2}$; the
pair $(e_{1},e_{2})$ is an _angle_ of $f$ at vertex $v$ (Fig. 2 highlights the
angles of a face $f$). Notice that if $v$ has exactly one incident edge $e$,
then $e_{1}=e_{2}=e$ and the pair $(e,e)$ is also an angle of $f$ at $v$. Let
$f$ be a face of $G$, let $v$ be a vertex of $f$, and let $(e_{1},e_{2})$ be
an angle of $f$ at $v$. Angle $(e_{1},e_{2})$ is a _source-switch_ of $f$ if
$e_{1}$ and $e_{2}$ are both outgoing edges for $v$; $(e_{1},e_{2})$ is a
_sink-switch_ of $f$ if $e_{1}$ and $e_{2}$ are both incoming edges for $v$.
An angle of $f$ that is neither a source-switch nor a sink-switch is a _non-
switch_ of $f$. It is easy to observe that for any face $f$ the number of
source-switches equals the number of sink-switches (in Fig. 2 the source- and
sink-switches of $f$ are indicated). The number of source-switches in a face
$f$ is denoted by $\mathcal{A}(f)$. The _capacity_ of $f$ is
$\mathcal{A}(f)+1$ if $f$ is the external face and it is $\mathcal{A}(f)-1$
otherwise.

###### Lemma 1

_[4]_ Let $G$ be a bimodal plane digraph. The number of source and sink
vertices of $G$ is equal to the sum of the capacities of the faces of $G$.

Let $G$ be an upward plane digraph and let $\Gamma$ be an embedding-preserving
upward planar drawing of $G$. The angles of $G$ correspond to geometric angles
in $\Gamma$. In particular, an angle $(e,e)$ of $G$ corresponds to a $2\pi$
angle in $\Gamma$. For each face $f$ of $G$, and for each source- or sink-
switch $a$ of $f$, we assign a label $L$ to $a$, if $a$ is larger than $\pi$
in $\Gamma$; in this case we say that $a$ is a _large angle_. Fig. 2 shows an
embedding-preserving upward planar drawing of the graph in Fig. 2 with the
angles larger that $\pi$ highlighted; the corresponding angles in Fig. 2 are
labeled with an $L$. We denote the number of $L$ labels on the angles of $f$
by $L(f)$. Also, if $v$ is a vertex of $G$, we denote by $L(v)$ the number of
$L$ labels on all angles at vertex $v$. In [4] it is shown that $L(v)=0$ if
$v$ is an internal vertex, and $L(v)=1$ if $v$ is a source or a sink. Also,
$L(f)=\mathcal{A}(f)+1$ if $f$ is the external face and
$L(f)=\mathcal{A}(f)-1$ otherwise; in other words, the number of large angles
inside each face is equal to its capacity (see, e.g., faces $f$ and
$f^{\prime}$ in Fig. 2).

A bimodal plane digraph $G$ is upward planar if and only if it is acyclic and
it admits an upward consistent assignment [4]. An _upward consistent
assignment_ is an assignment of the source and sink vertices of $G$ to its
faces such that: (i) Each source or sink $v$ is assigned to exactly one of its
incident faces. (ii) For each face $f$, the number of source and sink vertices
assigned to $f$ is equal to the capacity of $f$. Assigning a source or sink
$v$ to a face $f$ corresponds to assigning an $L$ label to an angle that $v$
forms in $f$. See Fig. 2 for an example.

Figure 2: (a) Angles (shown in gray), source-switches, and sink-switches of a
face $f$ of a bimodal plane digraph $G$; $\mathcal{A}(f)=2$; (b) An upward
planar drawing of $G$. (c) The assignments of $L$ labels to the angles of $G$
($L(f){=}1$, $L(f^{\prime}){=}3$).

$2$-subdivisions of bimodal plane digraphs. Let $G$ be a bimodal plane
digraph. A face $f$ of $G$ is _nice_ if $\delta(f)=4$ and each angle of $f$ is
either a source-switch or a sink-switch (see, e.g., $f_{2}$ in Fig. 3). We
augment $G$ by adding edges (possibly creating multiple edges) so that the
augmented digraph $G^{\prime}$ is bimodal and each face of $G^{\prime}$ either
has degree two, or three, or it is nice (note that there can be more than one
such augmentations). The resulting digraph is called a _quasi-triangulation_
of $G$ and all its faces have degree at most four. See Figs. 3 and 3. The
following lemma, whose proof is reported in the appendix for completeness, can
also be derived as a special case of [1, Lemma 5].

Figure 3: (a) A bimodal plane digraph $G$; $f_{2}$ is nice, while $f_{1}$ is
not; $f_{3}$ is such that $\delta(f_{3})\geq 5$. (b) A quasi-triangulation of
$G$: The added edges are colored blue.

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

Every bimodal plane digraph admits a quasi-triangulation.

The _$2$ -subdivision_ of a bimodal plane digraph $G$ is the graph $\hat{G}$
obtained from $G$ by replacing each edge $e=(u,v)$ of $G$ with the three edges
$(u,t_{e})$, $(s_{e},t_{e})$, $(s_{e},v)$, where $s_{e}$ and $t_{e}$ are two
subdivision vertices. See Fig. 4 for an illustration. Notice that $s_{e}$ is a
source and $t_{e}$ is a sink. Furthermore, the $2$-subdivision $\hat{G}$ of
$G$ is bimodal, it has no multiple edges, and it is acyclic even if $G$ is
not. We prove that $\hat{G}$ is upward planar, which implies that $G$ admits
an embedding preserving quasi-upward planar drawing with curve complexity two.
Since $\hat{G}$ is bimodal and acyclic, it is sufficient to prove that
$\hat{G}$ admits an upward consistent assignment. We model the problem of
computing an upward consistent assignment of $\hat{G}$ as a matching problem
on a suitably defined bipartite graph.

The _bipartite description_ of $\hat{G}$ is the bipartite graph
$H_{\hat{G}}=(A,B,E)$ defined as follows. The vertex set $A$ contains for each
face $\hat{f}$ of $\hat{G}$ a set of vertices
$a_{1}(\hat{f}),a_{2}(\hat{f}),\dots,a_{c}(\hat{f})$, where $c$ is the
capacity of $\hat{f}$. Each vertex $a_{i}(\hat{f})$ (for $i=1,\dots,c$) is
called a _representative vertex_ of face $f$. The vertex set $B$ contains the
source and sink vertices of $\hat{G}$. There is an edge $(a_{i}(\hat{f}),v)$
in $E$ if $v$ is a source or sink vertex of face $\hat{f}$ (for
$i=1,\dots,c$). See Fig. 4 for an illustration.

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

The $2$-subdivision of a bimodal plane digraph admits an upward consistent
assignment if and only if its bipartite description has a perfect matching.

A bimodal plane digraph is _face-acyclic_ if its face boundaries are not
cycles. To prove the main result of this section, we first consider face-
acyclic bimodal plane digraphs. We then show how to extend the result to the
general case.

###### Lemma 4

The $2$-subdivision of a face-acyclic bimodal plane digraph is upward planar.

###### Proof

Let $G$ be a face-acyclic bimodal plane digraph. We assume that $G$ is a
quasi-triangulation. If not, by Lemma 2 we can augment $G$ to a quasi-
triangulation and the statement follows because the $2$-subdivision of $G$ is
a subgraph of the $2$-subdivision of the obtained quasi-triangulation. By
Lemma 3, it suffices to prove that $H_{\hat{G}}$ has a perfect matching.
According to Hall’s theorem $H_{\hat{G}}=(A,B,E)$ has a perfect matching if
and only if for each $A^{\prime}\subseteq A$, we have that
$|A^{\prime}|\leq|N(A^{\prime})|$, where $N(A^{\prime})\subseteq B$ is the set
of neighbors of the vertices in $A^{\prime}$ [22]. Let $A^{\prime}$ be a
subset of $A$ and let $\\{f_{1},\dots,f_{k}\\}$ be the faces with a
representative vertex in $A^{\prime}$. $A^{\prime}$ is _complete_ if it
contains all representative vertices for each face $f_{i}$ ($1\leq i\leq k$).

Figure 4:  (a) The $2$-subdivision $\hat{G}$ of the graph $G$ in Fig. 3. (b) A
portion of the bipartite description $H_{\hat{G}}$ of $\hat{G}$.

###### Claim 1

Let $A^{\prime}$ and $A^{\prime\prime}$ be two distinct subsets of $A$ that
contain the representative vertices of the same set of faces. If $A^{\prime}$
is complete and $|A^{\prime}|\leq|N(A^{\prime})|$, then
$|A^{\prime\prime}|\leq|N(A^{\prime\prime})|$.

_Proof._ Since $A^{\prime\prime}\subseteq A^{\prime}$ and since all the
representative vertices of a face have the same neighbors in $B$, we have that
$|A^{\prime\prime}|\leq|A^{\prime}|$ and $N(A^{\prime})=N(A^{\prime\prime})$.
$\blacksquare$

By Claim 1, it is sufficient to prove that Hall’s theorem holds for any
complete subset $A^{\prime}$ of $A$. Let $N_{1}(A^{\prime})=\\{v\in
N(A^{\prime})~{}|~{}v$ is a subdivision vertex of $\hat{G}\\}$ and let
$N_{2}(A^{\prime})=N(A^{\prime})\setminus N_{1}(A^{\prime})$. Let $F$ be the
set of the faces of $G$ and let $F^{\prime}\subseteq F$ be the set of faces
whose representative vertices are in $A^{\prime}$. We denote by
$G_{F^{\prime}}$ the bimodal plane subgraph of $G$ induced by the edges of the
boundaries of the faces in $F^{\prime}$. Note that $G_{F^{\prime}}$ can have
faces other than those in $F^{\prime}$ (see Figs. 5 and 5). Let
$F^{\prime\prime}$ be the set of faces of $G_{F^{\prime}}$ that are not in
$F^{\prime}$. Each face in $F^{\prime\prime}$ is the union of one or more
faces of $F\setminus F^{\prime}$. Further, let $F^{\prime}_{i}=\\{f\in
F^{\prime}~{}|~{}f\text{ has degree $i$ in $G$}\\}$, for $i=2,3,4$. Let
$E_{b}$ be the set of edges of $G$ shared by the faces in $F^{\prime}$ and
those in $F^{\prime\prime}$ (bold edges in Fig. 5). Finally, we set $\alpha=1$
if the external face of $G$ belongs to $F^{\prime}$, and $\alpha=0$ otherwise.

###### Claim 2

$|N_{1}(A^{\prime})|-|A^{\prime}|=|E_{b}|-|F^{\prime}_{4}|-2\alpha$.

_Proof._ For each edge of $G_{F^{\prime}}$ there are two vertices in
$N_{1}(A^{\prime})$ because each edge has two subdivision vertices. Thus
$|N_{1}(A^{\prime})|=2|E_{b}|+2|E_{x}|$, where $E_{x}$ is the set of edges of
$G_{F^{\prime}}$ that are not in $E_{b}$.

Figure 5: Illustration for Lemma 4. (a) Faces in $F^{\prime}$ are gray. (b)
The graph $G_{F^{\prime}}$; faces of $F^{\prime\prime}$ are green. The red
vertex belongs to $S_{F^{\prime}}$. The edges of $E_{b}$ are bold.

Since $G$ is face-acyclic, each face of degree $2$ (resp. $3$ and $4$) in $G$
has capacity $2$ (resp. $3$ and $5$) in $\hat{G}$ if it is an internal face,
and it has capacity $4$ (resp. $5$ and $7$) if it is the external face. It
follows that for each face in $F^{\prime}_{2}$ there are two vertices in
$A^{\prime}$, for each face in $F^{\prime}_{3}$ there are three vertices in
$A^{\prime}$, and for each face in $F^{\prime}_{4}$ there are five vertices in
$A^{\prime}$. If the external face of $G$ belongs to $F^{\prime}$, then there
are two additional vertices in $A^{\prime}$. Thus,
$|A^{\prime}|=2|F^{\prime}_{2}|+3|F^{\prime}_{3}|+5|F^{\prime}_{4}|+2\alpha$
and
$|N_{1}(A^{\prime})|-|A^{\prime}|=2|E_{b}|+2|E_{x}|-2|F^{\prime}_{2}|-3|F^{\prime}_{3}|-5|F^{\prime}_{4}|-2\alpha$.

Each face in $F^{\prime}_{i}$ has $i$ edges in $G_{F^{\prime}}$, for
$i=2,3,4$. Each edge of $E_{x}$ belongs to two faces of $F^{\prime}$, while
each edge of $E_{b}$ belongs to only one face of $F^{\prime}$. Thus we have
$|E_{b}|+2|E_{x}|=2|F^{\prime}_{2}|+3|F^{\prime}_{3}|+4|F^{\prime}_{4}|$ and
therefore
$|N_{1}(A^{\prime})|-|A^{\prime}|=|E_{b}|+(2|F^{\prime}_{2}|+3|F^{\prime}_{3}|+4|F^{\prime}_{4}|)-2|F^{\prime}_{2}|-3|F^{\prime}_{3}|-5|F^{\prime}_{4}|-2\alpha=|E_{b}|-|F^{\prime}_{4}|-2\alpha$.
$\blacksquare$

Graph $G_{F^{\prime}}$ can have some source or sink vertices that are not
source or sink vertices of $G$ because $G_{F^{\prime}}$ has a subset of the
edges of $G$ (see for example the red vertex in Fig. 5). Let $S_{F^{\prime}}$
be the set of such vertices. Also, let $F^{\prime\prime}_{2}$ and
$F^{\prime\prime}_{3}$ be the set of faces of $F^{\prime\prime}$ that have
degree $2$ and $3$, respectively, in $G_{F^{\prime}}$ and let
$F^{\prime\prime}_{x}$ be the set
$F^{\prime\prime}\setminus(F^{\prime\prime}_{3}\cup F^{\prime\prime}_{2})$.

###### Claim 3

$|N_{2}(A^{\prime})|\geq|F^{\prime}_{4}|-\frac{|E_{b}|}{2}-\frac{|F^{\prime\prime}_{3}|}{2}-|F^{\prime\prime}_{2}|-|F^{\prime\prime}_{x}|+2$.

_Proof._ By Lemma 1, the number of source and sink vertices of
$G_{F^{\prime}}$ is equal to the total capacity of the faces of
$G_{F^{\prime}}$. The number of source and sink vertices of $G_{F^{\prime}}$
is $|N_{2}(A^{\prime})|+|S_{F^{\prime}}|$. The total capacity of the faces of
$G_{F^{\prime}}$ is given by two terms: The total capacity $C^{\prime}$ of the
faces in $F^{\prime}$ plus the total capacity $C^{\prime\prime}$ of the faces
in $F^{\prime\prime}$. We have $C^{\prime}=|F^{\prime}_{4}|+2\alpha$. Indeed,
let $f$ be a face of $F^{\prime}$: If $f$ is internal it has capacity $0$ if
it has degree $2$ or $3$ and it has capacity $1$ if it has degree $4$; if $f$
is the external face of $G_{F^{\prime}}$, it has capacity $2$ if it has degree
$2$ or $3$ and it has capacity $3$ if it has degree $4$. The term
$C^{\prime\prime}$ is equal to $\sum_{f\in
F^{\prime\prime}}(\mathcal{A}(f)-1)+2(1-\alpha)$, where $2(1-\alpha)$ takes
into account the fact that the external face of $G_{F^{\prime}}$ may belong to
$F^{\prime\prime}$. (Recall that the capacity of a face is $\mathcal{A}(f)-1$
if it is internal and $\mathcal{A}(f)+1$ if it is external. Also, if
$\alpha=1$ the external face of $G_{F^{\prime}}$ belongs to $F^{\prime}$,
otherwise it belongs to $F^{\prime\prime}$.)

Each vertex in $S_{F^{\prime}}$ belongs to at least one face of
$F^{\prime\prime}$. Let $v$ be a vertex of $S_{F^{\prime}}$ and let $f$ be a
face of $F^{\prime\prime}$ that contains $v$. Since $v$ is a source or a sink
vertex, $f$ has at least one angle at $v$ that is either a source-switch or a
sink-switch. In other words, for each vertex in $S_{F^{\prime}}$ there is at
least one source-switch or a sink-switch in a face of $F^{\prime\prime}$.
Since at least $\frac{|S_{F^{\prime}}|}{2}$ of these angles are source-
switches or sink-switches, we have that $\sum_{f\in
F^{\prime\prime}}\mathcal{A}(f)\geq\frac{|S_{F^{\prime}}|}{2}$ (recall that
$\mathcal{A}(f)$ is equal to the number of source-switches of $f$, which is
equal to the number of sink-switches of $f$). It follows that
$C^{\prime\prime}=\sum_{f\in
F^{\prime\prime}}(\mathcal{A}(f)-1)+2(1-\alpha)\geq\frac{|S_{F^{\prime}}|}{2}-|F^{\prime\prime}|+2(1-\alpha)$.

Thus, we have
$|N_{2}(A^{\prime})|+|S_{F^{\prime}}|=C^{\prime}+C^{\prime\prime}\geq|F^{\prime}_{4}|+2\alpha+\frac{|S_{F^{\prime}}|}{2}-|F^{\prime\prime}|+2(1-\alpha)$.
From $F^{\prime\prime}=F^{\prime\prime}_{2}\cup F^{\prime\prime}_{3}\cup
F^{\prime\prime}_{x}$, we obtain
$|N_{2}(A^{\prime})|\geq|F^{\prime}_{4}|-\frac{|S_{F^{\prime}}|}{2}-|F^{\prime\prime}_{2}|-|F^{\prime\prime}_{3}|-|F^{\prime\prime}_{x}|+2$.
Since each edge of $E_{b}$ is shared by a face of $F^{\prime}$ and a face of
$F^{\prime\prime}$ and since each face of $F^{\prime\prime}$ has only edges of
$E_{b}$ in its boundary, we have that $\sum_{f\in
F^{\prime\prime}}\delta(f)=|E_{b}|$. Also, each face in $F^{\prime\prime}_{3}$
has at most two switches and therefore at least one of its vertices does not
belong to $|S_{F^{\prime}}|$. It follows that $|S_{F^{\prime}}|\leq\sum_{f\in
F^{\prime\prime}}\delta(f)-|F^{\prime\prime}_{3}|=|E_{b}|-|F^{\prime\prime}_{3}|$,
and therefore
$|N_{2}(A^{\prime})|\geq|F^{\prime}_{4}|-\frac{|E_{b}|}{2}+\frac{|F^{\prime\prime}_{3}|}{2}-|F^{\prime\prime}_{2}|-|F^{\prime\prime}_{3}|-|F^{\prime\prime}_{x}|+2=|F^{\prime}_{4}|-\frac{|E_{b}|}{2}-\frac{|F^{\prime\prime}_{3}|}{2}-|F^{\prime\prime}_{2}|-|F^{\prime\prime}_{x}|+2$.
$\blacksquare$

In order to prove that the condition of Hall’s theorem holds for $A^{\prime}$,
we will show that $|N(A^{\prime})|-|A^{\prime}|\geq 0$. By Claims 2 and 3,
$|N(A^{\prime})|-|A^{\prime}|=|N_{1}(A^{\prime})|+|N_{2}(A^{\prime})|-|A^{\prime}|\geq|E_{b}|-|F^{\prime}_{4}|-2\alpha+|F^{\prime}_{4}|-\frac{|E_{b}|}{2}-\frac{|F^{\prime\prime}_{3}|}{2}-|F^{\prime\prime}_{2}|-|F^{\prime\prime}_{x}|+2=\frac{|E_{b}|}{2}-\frac{|F^{\prime\prime}_{3}|}{2}-|F^{\prime\prime}_{2}|-|F^{\prime\prime}_{x}|+2-2\alpha$.

Since the faces in $F^{\prime\prime}$ do not share edges, we have that
$|E_{b}|\geq
2|F^{\prime\prime}_{2}|+3|F^{\prime\prime}_{3}|+4|F^{\prime\prime}_{x}|$, and
therefore
$|N(A^{\prime})|-|A^{\prime}|\geq\frac{2|F^{\prime\prime}_{2}|}{2}+\frac{3|F^{\prime\prime}_{3}|}{2}+\frac{4|F^{\prime\prime}_{x}|}{2}-\frac{|F^{\prime\prime}_{3}|}{2}-|F^{\prime\prime}_{2}|-|F^{\prime\prime}_{x}|+2-2\alpha=|F^{\prime\prime}_{3}|+|F^{\prime\prime}_{x}|+2-2\alpha$.
Since $\alpha$ is either $0$ or $1$, we have that
$|N(A^{\prime})|-|A^{\prime}|\geq|F^{\prime\prime}_{3}|+|F^{\prime\prime}_{x}|\geq
0$ and the condition of Hall’s theorem holds.∎

The next theorem extends Lemma 4 to graphs that may not be face-acyclic.

######  Theorem 3.1 ()

The $2$-subdivision of a bimodal plane digraph is upward planar.

###### Proof

Let $G$ be a bimodal plane digraph. If $G$ is face-acyclic the statement
follows from Lemma 4. Otherwise, for every face $f$ of $G$ whose boundary is a
cycle, we insert a source vertex $v$ inside $f$ and connect it to every vertex
of the boundary of $f$. Let $G^{\prime}$ be the resulting digraph. Clearly,
$G^{\prime}$ is a face-acyclic bimodal digraph and by Lemma 4 the
$2$-subdivision $\hat{G^{\prime}}$ of $G^{\prime}$ is upward planar. Since the
$2$-subdivision of $G$ is a subgraph of $\hat{G^{\prime}}$, the statement
follows.∎

##  4 Computing Minimum Curve Complexity Drawings

To efficiently compute quasi-upward planar drawings with minimum curve
complexity, we define a variant of the flow network used by Bertolazzi et al.
[3]. Feasible flows in this network correspond to quasi-upward planar
drawings. Intuitively, each unit of flow represents a large angle; large
angles are produced by sources and sinks and are consumed by the faces.

Let $G$ be a bimodal plane digraph. The _unit-capacity flow network of $G$_,
denoted as $\mathcal{N}_{u}(G)$, is defined as follows (see Fig. 6). For each
edge $e$ of $\mathcal{N}_{u}(G)$, we denote by $\beta(e)$, $\chi(e)$ and
$\varphi(e)$ the capacity, the cost, and the flow of $e$, respectively.

  * •

The nodes of $\mathcal{N}_{u}(G)$ are all the sources and sinks (_vertex-
nodes_), and all the faces (_face-nodes_) of $G$.

  * •

Each vertex-node $v$ of $\mathcal{N}_{u}(G)$ supplies a flow equal to $1$.
This means that exactly one of the angles at $v$ must be large.

  * •

Each face-node of $\mathcal{N}_{u}(G)$ that corresponds to a face $f$ demands
a flow equal to the capacity of $f$. This means that $f$ must have a number of
large angles equal to its capacity. If $f$ is an internal face and it is a
directed cycle then $\mathcal{A}(f)=0$ and the capacity of $f$ is $-1$, that
is, $f$ supplies a flow equal to $1$.

  * •

For each source or sink $v$ that belongs to a face $f$, there is a _vertex-to-
face arc_ $(v,f)$ in $\mathcal{N}_{u}(G)$ such that $\beta(v,f)=1$ and
$\chi(v,f)=0$. Intuitively, a unit of flow on this arc means that $f$ has a
large angle at $v$.

  * •

For each edge $e$ of $G$ shared by two faces $f$ and $g$, there is a pair of
_face-to-face arcs_ $(f,g)$ and $(g,f)$ in $\mathcal{N}_{u}(G)$ such that
$\beta(f,g)=\beta(g,f)=1$ and $\chi(f,g)=\chi(g,f)=2$. Intuitively, a unit of
flow on $(f,g)$ or on $(g,f)$ represents the insertion of two bends along $e$.
This corresponds to two units of cost. The two arcs $(f,g)$ and $(g,f)$ are
called the _dual arcs_ of edge $e$.

Figure 6: (a) A bimodal planar embedding of the graph $G$ of Fig. 1. (b) The
unit-capacity flow network $\mathcal{N}_{u}(G)$. The dashed arcs (vertex-to-
face arcs) have cost 0, while solid arcs (face-to-face arcs) have cost $2$.
The number close to each face-node indicates the capacity of the face. (c) A
feasible flow $\varphi$ for $\mathcal{N}_{u}(G)$. A unit of flow traverses the
edges highlighted in bold. The cost of the flow is $2$. A $2$-bend drawing of
$G$ corresponding to $\varphi$ is the one shown in Fig. 1.

We remark that the main differences between the flow network defined above and
the flow network $\mathcal{N}(G)$ defined by Bertolazzi et al. [3] are as
follows: _(i)_ In $\mathcal{N}_{u}(G)$ we have two opposite face-to-face arcs
for each edge $e$ of $G$, while in $\mathcal{N}(G)$ there are two opposite
face-to-face arcs for each pair of adjacent faces, even when they share more
than one edge; _(ii)_ the capacity of the face-to-face arcs is one in
$\mathcal{N}_{u}(G)$ and it is unbounded in $\mathcal{N}(G)$. The fact that
$\mathcal{N}_{u}(G)$ is well-defined is a consequence of Lemma 1. The
following lemma will be used to prove that a quasi-upward planar drawing with
minimum curve complexity can be computed by means of the flow network
$\mathcal{N}_{u}(G)$.

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

Let $G$ be a bimodal plane digraph. For each feasible flow $\varphi_{u}$ in
$\mathcal{N}_{u}(G)$ there exists a quasi-upward planar drawing $\Gamma$ of
$G$ such that the number of bends along each edge $e$ of $G$ is equal to the
sum of the costs of the flows along the two face-to-face arcs that are the
dual arcs of $e$.

The next theorem gives the main result of this section and exploits the
algorithm by Karczmarz and Sankowski [25] to compute a min-cost flow on a
planar unit-capacity flow network.

######  Theorem 4.1 ($\star$)

Let $G$ be a bimodal plane digraph with $m$ edges. There exists an
${\tilde{O}}(m^{\frac{4}{3}})$-time algorithm that computes a quasi-upward
planar drawing $\Gamma$ of $G$ with the following properties:  (i) $\Gamma$has
minimum curve complexity, which is at most two.  (ii) $\Gamma$has the minimum
number of bends among the quasi-upward planar drawings of $G$ with minimum
curve complexity.

If $G$ does not have homotopic multiple edges (i.e., multiple edges that
define a face), then $m\in O(n)$ and the time complexity of Theorem 4.1 is
${\tilde{O}}(n^{\frac{4}{3}})$.

##  5 A Lower Bound on the Curve Complexity

By Theorem 4.1, every bimodal plane digraph admits a quasi-upward planar
drawing with curve complexity two, which is worst-case optimal. One may wonder
whether curve complexity two and minimum total number of bends can be
simultaneously achieved. The next lemma shows that this is not always
possible.

Figure 7: (a) Supplier gadget. (b) Barrier gadget. Figure 8: Graph $G_{6}$ in
the proof of Lemma 6. The blue arrow represents a path in the dual that is
shorter than the one represented by the red arrow. The green arrow also
represents a shortest path.

######  Lemma 6 ($\star$)

For every integer $k\geq 3$, there exists a bimodal planar acyclic digraph
$G_{k}$ with $14k-3$ vertices and $41k-13$ edges such that every quasi-upward
planar drawing of $G_{k}$ with the minimum number of bends has one edge with
at least $2k-2$ bends.

###### Sketch of proof

For each $k\geq 3$, we construct a graph $G_{k}$ by suitably combining
different copies of two gadgets. The first gadget is shown in Fig. 7 and it is
called _supplier gadget_ because it contains one source and one sink vertex,
denoted as $s$ and $t$ in Fig. 7, that supply two units of flow. Graph $G_{k}$
has $k$ copies of the supplier gadget that in total supply $2k$ units of flow;
$G_{k}$ is such that $k-1$ units of this flow have to reach a specific face.
To force these $k-1$ units of flow to “traverse” the same edge (thus creating
$2k-2$ bends along this edge), we use the second gadget, shown in Fig. 7. This
gadget is called _barrier gadget_ because it is used to prevent the flow to
traverse some edges. Graph $G_{k}$ is shown in Fig. 8 for $k=6$. See the
appendix for more details on the construction of $G_{k}$.

We now prove that every quasi-upward planar drawing of $G_{k}$ with the
minimum number of bends has at least one edge with at least $2k-2$ bends. Let
$\Gamma$ be any quasi-upward planar drawing of $G_{k}$ with the minimum number
of bends and let $\psi$ be the planar embedding of $\Gamma$. Drawing $\Gamma$
corresponds to a minimum cost flow on the flow network $\mathcal{N}(G_{k})$
defined on the planar embedding $\psi$ [3]. Since $G_{k}$ is triconnected, all
its planar embeddings have the same set of faces and each embedding is defined
by the choice of a face as the external one. Let $f^{*}$ be the face that is
external in the embedding of $G_{k}$ shown in Fig. 8. Face $f^{*}$ has $k$
source-switches, which implies that its capacity is at least $k-1$ in
$\mathcal{N}(G_{k})$: Namely, it is $k+1$ if $f^{*}$ is the external face in
$\psi$ and $k-1$ otherwise. Since there are one source and one sink in each of
the $k$ supplier gadgets, the total amount of flow consumed by the faces is
$2k$. In any planar embedding of $G_{k}$ the cycle $\eta$, highlighted by bold
edges in Fig. 8, separates the source and sink vertices from $f^{*}$. It
follows that at least $k-1$ units of flow must go through the dual arcs of the
edges of $\eta$, thus creating at least $2k-2$ bends along the edges of
$\eta$. We now prove that all these bends are on the edge $(s_{1},t_{k})$.
Consider a unit flow that goes from a source or a sink node $v$ to $f^{*}$
following a path $\pi$ in $\mathcal{N}(G_{k})$; the cost of sending this unit
of flow along $\pi$ is equal to the number of face-to-face arcs in $\pi$
because face-to-face arcs have cost two. Each face-to-face arc of $\pi$ is the
dual arc of an edge in $G_{k}$ shared by two adjacent faces. Hence, to obtain
a minimum cost flow, each unit of flow that goes from a source or a sink node
$v$ to $f^{*}$ in $\mathcal{N}(G_{k})$ follows a shortest path $\pi$ in the
dual graph of $G_{k}$ connecting a face incident to $v$ with $f^{*}$. The
lemma holds because any shortest path in the dual graph of $G_{k}$ connecting
a face incident to $v$ with $f^{*}$ includes a dual arc of the edge
$(s_{1},t_{k})$. (See the appendix for more details.) ∎

The next theorem extends the result of Lemma 6 to the cases when $n$ is not
equal to $14k-3$, for some $k>0$.

######  Theorem 5.1 ($\star$)

For every $n\geq 39$ there exists a bimodal planar digraph with $n$ vertices
such that every bend-minimum quasi-upward planar drawing has curve complexity
at least $\frac{n-24}{7}$.

##  6 Open Problems

We conclude by mentioning some open problems that are naturally suggested by
the results in this paper.

  * •

Is it possible to improve the time complexity stated by Theorem 4.1?

  * •

We showed that every bimodal plane digraph becomes upward planar if every edge
is subdivided twice. It would be interesting to minimize the total number of
subdivision vertices (with at most two subdivision vertices per edge) such
that the resulting graph admits an upward straight-line drawing of polynomial
area.

## References

  * [1] Angelini, P., Chaplick, S., Cornelsen, S., Da Lozzo, G.: Planar L-drawings of bimodal graphs. CoRR abs/2008.07834 (2020), https://arxiv.org/abs/2008.07834
  * [2] Bekos, M.A., Kaufmann, M., Krug, R.: On the total number of bends for planar octilinear drawings. J. Graph Algorithms Appl. 21(4), 709–730 (2017)
  * [3] Bertolazzi, P., Di Battista, G., Didimo, W.: Quasi-upward planarity. Algorithmica 32(3), 474–506 (2002). https://doi.org/10.1007/s00453-001-0083-x
  * [4] Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 12(6), 476–497 (1994). https://doi.org/10.1007/BF01188716
  * [5] Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159–180 (1998). https://doi.org/10.1016/S0925-7721(97)00026-6
  * [6] Binucci, C., Di Giacomo, E., Liotta, G., Tappini, A.: Quasi-upward planar drawings with minimum curve complexity. CoRR abs/2108.10784 (2021), https://arxiv.org/abs/2108.10784
  * [7] Binucci, C., Didimo, W.: Quasi-upward planar drawings of mixed graphs with few bends: Heuristics and exact methods. In: WALCOM. Lecture Notes in Computer Science, vol. 8344, pp. 298–309. Springer (2014)
  * [8] Binucci, C., Didimo, W.: Computing quasi-upward planar drawings of mixed graphs. Comput. J. 59(1), 133–150 (2016). https://doi.org/10.1093/comjnl/bxv082
  * [9] Binucci, C., Didimo, W., Patrignani, M.: Upward and quasi-upward planarity testing of embedded mixed graphs. Theor. Comput. Sci. 526, 75–89 (2014). https://doi.org/10.1016/j.tcs.2014.01.015
  * [10] Chan, H.: A parameterized algorithm for upward planarity testing. In: Albers, S., Radzik, T. (eds.) Algorithms – ESA 2004. pp. 157–168. Springer Berlin Heidelberg, Berlin, Heidelberg (2004)
  * [11] Chaplick, S., Lipp, F., Wolff, A., Zink, J.: Compact drawings of 1-planar graphs with right-angle crossings and few bends. Comput. Geom. 84, 50–68 (2019)
  * [12] Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River, NJ (1999)
  * [13] Di Battista, G., Tamassia, R., Tollis, I.G.: Area requirement and symmetry display of planar upward drawings. Discret. Comput. Geom. 7, 381–401 (1992). https://doi.org/10.1007/BF02187850
  * [14] Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H.: Area, curve complexity, and crossing resolution of non-planar graph drawings. In: Graph Drawing. Lecture Notes in Computer Science, vol. 5849, pp. 15–20. Springer (2009)
  * [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). https://doi.org/10.1007/s00453-008-9255-2
  * [17] Didimo, W.: Upward graph drawing. In: Encyclopedia of Algorithms, pp. 2308–2312 (2016). https://doi.org/10.1007/978-1-4939-2864-4_653
  * [18] Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. SIAM J. Discret. Math. 23(4), 1842–1899 (2009). https://doi.org/10.1137/070696854
  * [19] Didimo, W., Liotta, G., Ortali, G., Patrignani, M.: Optimal orthogonal drawings of planar 3-graphs in linear time. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. pp. 806–825. SIAM (2020). https://doi.org/10.1137/1.9781611975994.49
  * [20] Didimo, W., Liotta, G., Patrignani, M.: Bend-minimum orthogonal drawings in quadratic time. In: Biedl, T.C., Kerren, A. (eds.) Graph Drawing and Network Visualization - 26th International Symposium, GD 2018. Lecture Notes in Computer Science, vol. 11282, pp. 481–494. Springer (2018). https://doi.org/10.1007/978-3-030-04414-5_34
  * [21] Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001). https://doi.org/10.1137/S0097539794277123
  * [22] Hall, P.: On representatives of subsets. J. London Math. Soc. s1-10(1), 26–30 (1935)
  * [23] Healy, P., Lynch, K.: Two fixed-parameter tractable algorithms for testing upward planarity. Int. J. Found. Comput. Sci. 17(5), 1095–1114 (2006). https://doi.org/10.1142/S0129054106004285
  * [24] Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996). https://doi.org/10.1007/BF02086606
  * [25] Karczmarz, A., Sankowski, P.: Min-cost flow in unit-capacity planar graphs. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019. LIPIcs, vol. 144, pp. 66:1–66:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.ESA.2019.66
  * [26] Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Algorithms Appl. 6(1), 115–129 (2002). https://doi.org/10.7155/jgaa.00046
  * [27] Kindermann, P., Montecchiani, F., Schlipf, L., Schulz, A.: Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles. Journal of Graph Algorithms and Applications 25(1), 1–28 (2021). https://doi.org/10.7155/jgaa.00547
  * [28] Rahman, M.S., Nakano, S., Nishizeki, T.: A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs. J. Graph Algorithms Appl. 3(4), 31–62 (1999). https://doi.org/10.7155/jgaa.00017
  * [29] Tamassia, R., Tollis, I.G., Vitter, J.S.: Lower bounds and parallel algorithms for planar orthogonal grid drawings. In: Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, SPDP 1991, 2-5 December 1991, Dallas, Texas, USA. pp. 386–393. IEEE Computer Society (1991). https://doi.org/10.1109/SPDP.1991.218215

## Appendix

##  Appendix 0.A Additional Material for Section 3

See 2

###### Proof

Let $G$ be a bimodal plane digraph. We prove that until $G$ has a face $f$
whose degree is larger than $4$ or it is not nice, we can add an edge inside
$f$ without violating the bimodality. If $f$ is a face of degree four that is
not nice, then it has an angle $(e_{1},e_{2})$ at a vertex $w$ that is a non-
switch. In this case, it is possible to add an edge between the end-vertices
of $e_{1}$ and $e_{2}$ different from $w$ without violating the bimodality
(see $f_{1}$ in Fig. 3). Let $f$ be a face of $G$ such that $\delta(f)\geq 5$.
If $f$ has an angle $(e_{1},e_{2})$ at a vertex $w$ that is a non-switch, we
can proceed as in the previous case. If all angles of $f$ are source- and
sink-switches, since $\delta(f)\geq 5$ there are a source-switch at a vertex
$u$ and a sink-switch at a vertex $v$ such that $u\neq v$ and $u$ and $v$ are
not adjacent in the boundary of $f$. It follows that it is possible to add
edge $(u,v)$ inside $f$ (see $f_{3}$ in Fig. 3). ∎

See 3

###### Proof

Let $G$ be a bimodal plane digraph. Suppose first that $G$ admits an upward
consistent assignment. According to this assignment each source or sink vertex
is assigned to a face and the number of source and sink vertices assigned to a
face is equal to its capacity. Let $v_{1},v_{2},\dots,v_{c}$ be the source and
sink vertices assigned to a face $f$ (where $c$ is the capacity of $f$). We
select the edges $(a_{i}(\hat{f}),v_{i})$ of $H_{\hat{G}}$ (for
$i=1,2,\dots,c$). Since the selected edges are independent, they are part of a
matching, and since exactly one edge is selected for each vertex
$a_{i}(\hat{f})$, the matching is perfect.

Suppose now that $H_{\hat{G}}$ has a perfect matching. For each face $f$ of
$G$ with capacity $c$, let $(a_{i}(\hat{f}),v_{i})$ (for $i=1,2,\dots,c$) be
the edges of $H_{\hat{G}}$ that belong to the perfect matching. We assign
vertices $v_{1},v_{2},\dots,v_{c}$ to face $f$. Clearly, each source or sink
vertex of $G$ is assigned to a face of $G$ and the number of source and sink
vertices that are assigned to each face of $G$ is equal to its capacity.∎

##  Appendix 0.B Additional Material for Section 4

See 5

###### Proof

The flow network $\mathcal{N}(G)$ is equivalent to a flow network
$\mathcal{N}^{+}(G)$ obtained as follows. Let $f$ and $g$ be two faces of $G$
that share edges $e_{1},e_{2},\dots,e_{k}$, for $k\geq 1$. The face-to-face
arc $(f,g)$ of $\mathcal{N}(G)$ is replaced in $\mathcal{N}^{+}(G)$ by a set
of face-to-face arcs $a_{1},a_{2},\dots,a_{k}$ such that each $a_{i}$ has
unbounded capacity and unit cost. Such a network coincides with
$\mathcal{N}_{u}(G)$ where all edges have unbounded capacity. Clearly, any
feasible flow $\varphi_{u}$ of $\mathcal{N}_{u}(G)$ is also a feasible flow of
$\mathcal{N}^{+}(G)$. As a consequence of [3, Lemma 7], a feasible flow in
$\mathcal{N}^{+}(G)$ corresponds to a quasi-upward planar drawing such that
the number of bends along each edge $e$ of $G$ is equal to the sum of the
costs of the flows along the two dual arcs of $e$.∎

See 4.1

###### Proof

To construct the drawing $\Gamma$ we compute a min-cost flow on
$\mathcal{N}_{u}(G)$. Denote by $n$, $m$, and $f$, the number of vertices,
edges and faces of $G$, respectively. Since $G$ is connected and planar, $n\in
O(m)$ and $f\in O(m)$. (We remark that although $G$ is planar, in general it
is not true that $m\in O(n)$ because $G$ has multiple edges.) Thus,
$\mathcal{N}_{u}(G)$ has $O(m)$ nodes and arcs, and it can be constructed in
$O(m)$ time. Since $\mathcal{N}_{u}(G)$ is planar and each edge has unit
capacity, we can use the algorithm by Karczmarz and Sankowski [25], whose time
complexity is ${\tilde{O}}((NM)^{\frac{2}{3}}\log C)$, where $N$ and $M$ are
the number of vertices and edges of the flow network, respectively, and $C$ is
an upper bound to the edge costs. For our flow network $\mathcal{N}_{u}(G)$,
we have $N\in O(m)$, $M\in O(m)$ and $C\in O(1)$. Thus, we can compute a min-
cost flow on $\mathcal{N}_{u}(G)$ in ${\tilde{O}}(m^{\frac{4}{3}})$ time. Once
a min-cost flow is computed, a drawing $\Gamma$ of $G$ can be constructed in
$O(m+b)$ time [12], where $b$ is the total number of bends. We now show that
the curve complexity of $\Gamma$ is two and therefore $b\in O(m)$.

By Lemma 5, the computed flow defines a drawing $\Gamma$ such that the number
of bends along an edge $e$ of $G$ is equal to the sum of the costs of the
flows along the two face-to-face arcs that are dual of $e$. Since the capacity
of the arcs is one, then each arc has at most one unit of flow; since the flow
has minimum cost, the dual arcs of an edge $e$ cannot have both one unit of
flow. It follows that each edge of $G$ has at most two bends. Moreover, if $G$
is upward planar (i.e., it can be drawn without bends), then the face-to-face
arcs have zero unit of flow, because they are the only arcs having an
associated cost. So the curve complexity of the computed drawing is minimum.
The fact that the flow has minimum cost implies that $\Gamma$ has the minimum
number of bends among all quasi-upward planar drawings with minimum curve
complexity. ∎

##  Appendix 0.C Additional Material for Section 5

See 6

###### Proof

For each $k\geq 3$, we construct a graph $G_{k}$ by suitably combining
different copies of two gadgets. The first gadget is shown in Fig. 7 and it is
called _supplier gadget_ because it contains one source and one sink vertex,
denoted as $s$ and $t$ in Fig. 7, that supply two units of flow. The edge
connecting the two vertices denoted as $a$ and $b$ in Fig. 7 is called the
_base_ of the supplier gadget, while the vertex denoted as $c$ is called the
_apex_ of the supplier gadget. Graph $G_{k}$ has $k$ copies of the supplier
gadget that in total supply a $2k$ units of flow; $G_{k}$ is such that at
least $k-1$ units of this flow have to reach a specific face. To force these
$k-1$ units of flow to “traverse” the same edge (thus creating $2k-2$ bends
along this edge) we use the second gadget, which is shown in Fig. 7. This
gadget is called _barrier gadget_ because it is used to prevent the flow to
traverse some edges. Similar to the supplier gadget, the edge connecting the
two vertices denoted as $x$ and $y$ in Fig. 7 is called the _base_ of the
barrier gadget, while the vertex denoted as $z$ is called the _apex_ of the
barrier gadget.

More precisely, $G_{k}$ is constructed as follows. See Fig. 8 for an
illustration. Let $\eta$ be a cycle consisting of $2k$ vertices $s_{1}$,
$t_{1}$, $s_{2}$, $t_{2}$, $\dots$, $s_{k}$, $t_{k}$, in this cyclic order
(highlighted by bold edges in Fig. 8). The edges of the cycle are oriented so
that each $s_{i}$ is a source and each $t_{i}$ is a sink. The graph $G_{k}$
contains $k$ copies $S_{1},S_{2},\dots,S_{k}$ of the supplier gadget. These
copies are arranged so that the base $(a_{i},b_{i})$ of gadget $S_{i}$
coincides with edge $(s_{i},t_{i})$ of cycle $\eta$, for $i=1,2,\dots,k$, and
the gadget is embedded inside the cycle $\eta$. The apices
$c_{1},c_{2},\dots,c_{k}$ of the supplier gadgets are connected with edges
$(c_{i},c_{i+1})$, for $i=1,2,\dots,k-1$, and edge $(c_{1},c_{k})$; notice
that edge $(c_{1},c_{k})$ is oppositely oriented with respect to the other
edges. The graph $G_{k}$ has $2k-1$ copies of the barrier gadget; $k$ of these
gadgets are denoted $B_{1},B_{2},\dots,B_{k}$, while the other $k-1$ are
denoted as $B^{\prime}_{1},B^{\prime}_{2},\dots,B^{\prime}_{k-1}$. These
copies are arranged so that: (i) the base $(x_{i},y_{i})$ of the gadget
$B_{i}$ coincides with edge $(s_{i},t_{i})$ of $\eta$, for $i=1,2,\dots,k$,
and the gadget is embedded outside the cycle $\eta$; (ii) the base
$(x^{\prime}_{i},y^{\prime}_{i})$ of the gadget $B^{\prime}_{i}$ coincides
with edge $(s_{i+1},t_{i})$ of $\eta$, for $i=1,2,\dots,k-1$, and the gadget
is embedded outside the cycle $\eta$. Notice that the gadgets in the second
set are mirrored with respect to the ones of the first set (i.e., their bases
are oppositely oriented). The apices of these gadgets are connected with edges
$(z^{\prime}_{i},z_{i})$ and $(z^{\prime}_{i},z_{i+1})$, for
$i=1,2,\dots,k-1$. Note that the graph $G_{k}$ is acyclic.

We now prove that every quasi-upward planar drawing of $G_{k}$ with the
minimum number of bends has at least one edge with at least $2k-2$ bends. Let
$\Gamma$ be any quasi-upward planar drawing of $G_{k}$ with the minimum number
of bends and let $\psi$ be the planar embedding of $\Gamma$. Drawing $\Gamma$
corresponds to a minimum cost flow on the flow network $\mathcal{N}(G_{k})$
defined on the planar embedding $\psi$ [3]. Since $G_{k}$ is triconnected all
its planar embeddings have the same set of faces and each embedding is defined
by the choice of a face as the external one. Let $f^{*}$ be the face that is
external in the embedding of $G_{k}$ shown in Fig. 8. Face $f^{*}$ has $k$
source-switches, which implies that its capacity is at least $k-1$ in
$\mathcal{N}(G_{k})$: Namely, it is $k+1$ if $f^{*}$ is the external face in
$\psi$ and $k-1$ otherwise. Since there are one source and one sink in each of
the $k$ supplier gadgets, the total amount of flow consumed by the faces is
$2k$. In any planar embedding of $G_{k}$ the cycle $\eta$, highlighted by bold
edges in Fig. 8, separates the source and sink vertices from $f^{*}$. It
follows that at least $k-1$ units of flow must go through the dual arcs of the
edges of $\eta$, thus creating at least $2k-2$ bends along the edges of
$\eta$. We now prove that all these bends are on the edge $(s_{1},t_{k})$.
Consider a unit flow that goes from a source or a sink node $v$ to $f^{*}$
following a path $\pi$ in $\mathcal{N}(G_{k})$; the cost of sending this unit
of flow along $\pi$ is equal to twice the number of face-to-face arcs in $\pi$
because face-to-face arcs have cost two. Each face-to-face arc of $\pi$ is the
dual arc of an edge in $G_{k}$ shared by two adjacent faces. It follows that
in order to obtain a minimum cost flow, each unit of flow that goes from a
source or a sink node $v$ to $f^{*}$ in $\mathcal{N}(G_{k})$ follows a
shortest path in the dual graph of $G_{k}$ connecting a face incident to $v$
with $f^{*}$. If $\pi$ in the dual graph of $G_{k}$ includes a dual arc of an
edge $e$, we say that $\pi$ _traverses_ $e$. We now show that any shortest
path in the dual graph of $G_{k}$ connecting a face incident to $v$ with
$f^{*}$ traverses edge $(s_{1},t_{k})$.

Let $v$ be a source or sink node of a supplier gadget $S_{i}$ different from
the source of $S_{1}$ and from the sink of $S_{k}$. There exists a path of
length $5$ from a face incident to $v$ to $f^{*}$ that traverses
$(s_{1},t_{k})$ (see the blue path in Fig. 8); such a path traverses two edges
of $S_{i}$, either edge $(c_{i-1},c_{i})$ or edge $(c_{i},c_{i+1})$, edge
$(c_{1},c_{k})$, and edge $(s_{1},t_{k})$. If a path from a face incident to
$v$ to $f^{*}$ exits $\eta$ by traversing an edge $e$ different from
$(s_{1},t_{k})$, then it must traverse the barrier gadget whose base coincides
with $e$, and thus its length is greater than $5$ (see the red path in Fig.
8). Consider now the source of $S_{1}$ and the sink of $S_{k}$. In this case,
there exists a path of length $3$ from a face incident to these vertices to
$f^{*}$ that traverses $(s_{1},t_{k})$ (see the green path in Fig. 8); this
path traverses two edges of $S_{i}$ ($i\in\\{1,k\\}$) and edge
$(s_{1},t_{k})$. Also in this case, any path that exits $\eta$ by traversing
an edge different from $(s_{1},t_{k})$ must traverse a barrier gadget, and
thus its length is greater than $3$. From the discussion above, it follows
that a flow of minimum cost in $\mathcal{N}(G_{k})$ has at least $k-1$ units
of flow that traverse $(s_{1},t_{k})$. ∎

See 5.1

###### Proof

Given an integer $n\geq 39$, let
$k=\left\lfloor\frac{n+3}{14}\right\rfloor\geq 3$. We construct a bimodal
planar graph $G$ starting from the graph $G_{k}$ defined in the proof of Lemma
6 and by adding to it $h=n-(14k-3)$ vertices connecting each of them to
$z^{\prime}_{1}$ with an edge outgoing from $z^{\prime}_{1}$. Notice that
$h\leq 13$ and that these vertices are all sinks. It follows that each of them
increases by one unit the capacity of the face inside which it is embedded,
and it also supplies one unit of flow. Since the length of the shortest path
from a source or sink vertex of a supplier gadget to face $f^{*}$ is smaller
that then length of the shortest path from the same source or sink vertex to
each of the faces where these additional vertices can be embedded, the
argument used in the proof of Lemma 6 still holds. It follows that $G$ has
curve complexity at least $2k-2=2(\frac{n-h+3}{14})-2=\frac{n-h-11}{7}$. Since
$h\leq 13$, the curve complexity is at least $\frac{n-24}{7}$.∎