Path-Monotonic Upward Drawings of Graphs

Abstract

In this paper, we introduce a new problem of finding an upward drawing of a given plane graph $\gamma$ with a set $\mathcal {P}$ of paths so that each path in the set is drawn as a poly-line that is monotone in the y-coordinate. We present a sufficient condition for an instance $(\gamma ,\mathcal {P})$ to admit such an upward drawing. We also present a linear-time algorithm to construct such a drawing, which is straight-line for a simple graph, or poly-line otherwise. Our results imply that every 1-plane graph admits an upward drawing.

Research supported by ARC Discovery Project. For omitted proofs, see  [12].

1 Introduction

Upward planar drawings of digraphs are well studied problem in Graph Drawing  [3]. In an upward planar drawing of a directed graph, no two edges cross and each edge is a curve monotonically increasing in the vertical direction. It was shown that an upward planar graph (i.e., a graph that admits an upward planar drawing) is a subgraph of a planar st-graph and admits a straight-line upward planar drawing  [4, 13], although some digraphs may require exponential area  [3]. Testing upward planarity of a digraph is NP-complete  [10]; a polynomial-time algorithm is available for an embedded triconnected digraph  [2].

Upward embeddings and orientations of undirected planar graphs were studied in  [6]. Computing bimodal and acyclic orientations of mixed graphs (i.e., graphs with undirected and directed edges) is known to be NP-complete  [14], and upward planarity testing for embedded mixed graph is NP-hard  [5]. Upward planarity can be tested in cubic time for mixed outerplane graphs, and linear-time for special classes of mixed plane triangulations  [8].

A monotone drawing is a straight-line drawing such that for every pair of vertices there exists a path that monotonically increases with respect to some direction. In an upward drawing, each directed path is monotone, and such paths are monotone with respect to the same (vertical) line, while in a monotone drawing, each monotone path is monotone with respect to a different line in general. Algorithms for constructing planar monotone drawings of trees and biconnected planar graphs are presented  [1].

In this paper, we introduce a new problem of finding an upward drawing of a given plane graph $\gamma$ together with a set $\mathcal {P}$ of paths so that each path in the set is drawn as a poly-line that is monotone in the y-coordinate. Let $\gamma =(V,E,F)$ be a plane graph and D be an upward drawing of $\gamma$. We call D monotonic to a path P of (V, E) if D is upward in the y-coordinate and the drawing induced by path P is y-monotone. We call D monotonic to a set of paths $\mathcal {P}$ if D is monotonic to each path in $\mathcal {P}$. More specifically, we initiate the following problem.

Path-monotonic Upward Drawing

Input: A connected plane graph $\gamma$, a set $\mathcal {P}$ of paths of length at least 2 and two outer vertices s and t.

Output: An (s, t)-upward drawing of $\gamma$ that is monotonic to $\mathcal {P}$.

We present a sufficient condition for an instance $(\gamma , \mathcal {P})$ to admit an (s, t)-upward drawing of $\gamma$ that is monotonic to $\mathcal {P}$ for any two outer vertices $s,t\not \in V_{\mathrm {inl}}(\mathcal {P})$ (see Theorem 1). We also present a linear-time algorithm to construct such a drawing, which is straight-line for a simple graph, or poly-line otherwise.

Then we apply the result to a problem of finding an upward drawing of a non-planar embedding of a graph (Theorem 2), and prove that every 1-plane graph (i.e., a graph embedded with at most one crossing per edge) admits an (s, t)-upward poly-line drawing (Corollary 1). Note that there is a 1-plane graph that admits no straight-line drawing  [17], and there is a 2-plane graph with three edges that admits no upward drawing.

Figure 1(a) shows an instance $(\gamma ,\mathcal {P})$ with $\mathcal {P}=\{ P_1=(v_6,u_1,v_2), P_2=(v_1,u_1,v_5), P_3=(v_3,u_2,v_4), P_4=(v_3,u_3,u_4,v_9), P_5=(v_{11},u_5,u_4,v_8), P_6=(v_{10},u_5,u_3,v_7), P_7=(v_{10},u_6,u_4,v_7),$ $P_8=(v_{12},u_7,v_{14}), P_9=(v_{10},u_7,v_{13}) \}$. Figure 1(b) shows an (s, t)-upward drawing monotonic to $\mathcal {P}$ such that each path is drawn as a poly-line monotone in the y-coordinate for $s=v_5$ and $t=v_8$.

Fig. 1.

(a) plane graph $\gamma$ with a path set $\mathcal {P}$ and a cycle set $\mathcal {C}$, where the edges in paths in $\mathcal {P}$ (resp., cycles $\mathcal {C}$) are depicted with black thick lines (resp., gray thick lines), and the vertices in $V_{\mathrm {inl}}$ (resp., $V_{\mathrm {end}}$ and $V\setminus V_{\mathrm {inl}}\cup V_{\mathrm {end}}$) are depicted with white circles (resp., gray circles and white squares); (b) $(s=v_5,t=v_8)$-upward poly-line drawing monotonic to $\mathcal {P}$.

2 Preliminaries

Graphs. In this paper, a graph stands for an undirected multiple graph without self-loops. A graph with no multiple edges is called simple. Given a graph $G = (V, E)$, the vertex and edge sets are denoted by V(G) and E(G), respectively.

A path P that visits vertices $v_1,v_2,\ldots ,v_{k+1}$ in this order is denoted by $P=(v_1,v_2,\ldots ,v_{k+1})$, where vertices $v_1$ and $v_{k+1}$ are called the end-vertices. Paths and cycles are simple unless otherwise stated.

A path with end-vertices $u,v\in V$ is called a u, v-path. A u, v-path that is a subpath of a path P is called the sub-u, v-path of P. Denote the set of end-vertices (resp., internal vertices) of all paths in a set $\mathcal {P}$ of paths by $V_{\mathrm {end}}(\mathcal {P})$ (resp., $V_{\mathrm {inl}}(\mathcal {P})$), which is written as $V_{\mathrm {end}}(P)$ (resp., $V_{\mathrm {inl}}(P)$) for $\mathcal {P}=\{P\}$.

Let G be a graph with a vertex set V with $n=|V|$ and an edge set E, and $N_G(v)$ denote the set of neighbors of a vertex v in G. Let X be a subset of V, and G[X] denote the subgraph of G induced by the vertices in X. We denote by $N_G(X)$ the set of neighbors of X; i.e., $N_G(X)=\cup _{v\in X}N_G(v)\setminus X$. A connected component H of G may be denoted with the vertex subset V(H) for simplicity.

For two distinct vertices $a,b\in V$, a bijection $\rho :V\rightarrow \{1,2,\ldots ,n\}$ is called an st-numbering if $\rho (a)=1$, $\rho (b)=n$, and each vertex $v\in V\setminus \{a,b\}$ has a neighbor $v'\in N_G(v)$ with $\rho (v')<\rho (v)$ and a neighbor $v''\in N_G(v)$ with $\rho (v)<\rho (v'')$. It is possible to find an st-numbering of a given graph with designated vertices a and b (if one exists) in linear time using depth-first search  [7, 16]. A biconnected graph admits an st-numbering for any specified vertices a and b.

Digraphs. Let $G = (V,E)$ be a digraph. The indegree (resp., outdegree) of a vertex $v\in V$ in G is defined to be the number of edges whose head is v (resp., whose tail is v). A source (resp., sink) is defined to be a vertex of indegree (resp., outdegree) 0. When G has no directed cycle, it is called acyclic. A digraph with n vertices is acyclic if and only if it admits a topological ordering, i.e., a bijection $\tau :V\rightarrow \{1,2,\ldots ,n\}$ such that $\tau (u)<\tau (v)$ for any directed edge (u, v).

We define an orientation of a graph $G=(V,E)$ to be a digraph $\widetilde{G}=(V,\widetilde{E})$ obtained from the graph by replacing each edge uv in G with one of the directed edge (u, v) or (v, u). A bipolar orientation (or st-orientation) of a graph is defined to be an acyclic digraph with a single source s and a single sink t  [9, 15], where we call such a bipolar orientation an (s, t)-orientation. A graph has a bipolar orientation if and only if it admits an st-numbering. Figure 1(b) illustrates an (s, t)-orientation for $s=v_5$ and $t=v_8$.

Lemma 1

For any vertices s and t in a biconnected graph G possibly with multiple edges, an (s, t)-orientation $\widetilde{G}$ of G can be constructed in linear time.

We call an orientation $\widetilde{G}$ of G compatible to a set $\mathcal {P}$ of paths in G if each path in $\mathcal {P}$ is directed from one end-vertex to the other in $\widetilde{G}$. The orientation in Fig. 1(b) is compatible to the path set $\mathcal {P}$.

Embeddings. An embedding $\varGamma$ of a graph (or a digraph) $G=(V,E)$ is a representation of G (possibly with multiple edges) in the plane, where each vertex in V is a point and each edge $e\in E$ is a curve (a Jordan arc) between the points representing its end-vertices. We say that two edges cross if they have a point in common, called a crossing, other than their endpoints.

To avoid pathological cases, standard non-degeneracy conditions apply: (i) no edge contains any vertex other than its endpoints; (ii) no edge crosses itself; (iii) no two edges meet tangentially; and (iv) two edges cross at most one point, and two crossing edges share no end-vertex (where two edges may share the two end-vertices). In this paper, we allow three or more edges to share the same crossing. An edge that does not cross any other edge is called crossing-free.

Let $\varGamma$ be an embedding of a graph (or digraph) $G=(V,E)$. We call $\varGamma$ a poly-line drawing if each edge $e\in E$ is drawn as a sequence of line segments. The point where two consecutive line segments meet is called a bend. We call a poly-line drawing a straight-line drawing if it has no bend.

We call a curve in the xy-plane y-monotone if the y-coordinate of the points in the curve increases from one end of the curve to the other. We call $\varGamma$ an upward drawing if (i) there is a direction d to be defined as the y-coordinate such that the curve for each edge $e\in E$ is y-monotone; and (ii) when G is a digraph, the head of e has a larger y-coordinate than that of the tail of e.

For two vertices $s,t\in V$, we call $\varGamma$ an (s, t)-upward drawing if $\varGamma$ is upward in the y-coordinate and the y-coordinate of s (resp., t) in $\varGamma$ is uniquely minimum (resp., maximum) among the y-coordinates of vertices in $\varGamma$. Figure 1(b) shows an example of an (s, t)-upward poly-line drawing with $s=v_5$ and $t=v_8$.

Plane Graphs. An embedding of a graph G with no crossing is called a plane graph and is denoted by a tuple (V, E, F) of a set V of vertices, a set E of edges and a set F of faces. We call a plane graph pseudo-simple if it has no pair of multiple edges e and $e'$ such that the cycle formed by e and $e'$ encloses no vertex.

Let $\gamma =(V,E,F)$ be a plane graph. We say that two paths P and $P'$ in $\gamma$ intersect if they are edge-disjoint and share a common internal vertex w, and the edges uw and wv in P and $u'w$ and $wv'$ in $P'$ incident to w appear alternately around w (i.e., in one of the orderings $u,u',v,v'$ and $u,v',v,u'$).

Let C be a cycle in $\gamma$. Define $V_{\mathrm {enc}}(C;\gamma )$, $E_{\mathrm {enc}}(C;\gamma )$ and $F_{\mathrm {enc}}(C;\gamma )$ to be the sets of vertices $v\in V\setminus V(C)$, edges $e\in E\setminus E(C)$ and inner faces $f\in F$ that are enclosed by C. The interior subgraph $\gamma [C]_{\mathrm {enc}}$ induced from $\gamma$ by C is defined to be the plane graph $(V(C)\cup V_{\mathrm {enc}}(C;\gamma ), E(C)\cup E_{\mathrm {enc}}(C;\gamma ), F_{\mathrm {enc}}(C;\gamma )\cup \{f_C\})$, where $f_C$ denotes the new outer face whose facial cycle is C. The exterior subgraph induced from $\gamma$ by C is defined to be the plane graph $(V\setminus V_{\mathrm {enc}}(C;\gamma ), E\setminus E_{\mathrm {enc}}(C;\gamma ), F\cup \{f_C\} \setminus F_{\mathrm {enc}}(C;\gamma ))$, where $f_C$ denotes the new inner face whose facial cycle is C. Note that when $\gamma$ is biconnected, the graph $\gamma [C]_{\mathrm {enc}}$ remains biconnected, since every two vertices $u,v\in V\setminus V_{\mathrm {enc}}(C;\gamma )$ have two internally disjoint paths without using edges in $E_{\mathrm {enc}}(C;\gamma )$.

We say that two cycles C and $C'$ in $\gamma$ intersect if $F_{\mathrm {enc}}(C;\gamma )\setminus F_{\mathrm {enc}}(C';\gamma )\ne \emptyset \ne F_{\mathrm {enc}}(C';\gamma )\setminus F_{\mathrm {enc}}(C;\gamma )$. Let $\mathcal {C}$ be a set of cycles in $\gamma$. We call $\mathcal {C}$ inclusive if no two cycles in $\mathcal {C}$ intersect. When $\mathcal {C}$ is inclusive, the inclusion-forest of $\mathcal {C}$ is defined to be a forest $\mathcal {I}=(\mathcal {C},\mathcal{E})$ of a disjoint union of rooted trees such that (i) the cycles in $\mathcal {C}$ are regarded as the vertices of $\mathcal {I}$; and (ii) a cycle C is an ancestor of a cycle $C'$ in $\mathcal {I}$ if and only if $F_{\mathrm {enc}}(C';\gamma )\subseteq F_{\mathrm {enc}}(C;\gamma )$. Let $\mathcal {I}(\mathcal {C})$ denote the inclusion-forest of $\mathcal {C}$.

An st-planar graph is defined to be a bipolar orientation of a plane graph for which both the source and the sink of the orientation are on the outer face of the graph. A directed acyclic graph G has an upward planar drawing if and only if G is a subgraph of an st-planar graph  [4, 13]. Every st-planar graph can have a dominance drawing [3], in which for every two vertices u and v there exists a path from u to v if and only if both coordinates of u are smaller than the corresponding coordinates of v. The following result is known.

Lemma 2

[3] (i) Every simple st-planar graph admits an upward straight-line drawing;

(ii) Every st-planar graph with multiple edges admits an upward poly-line drawing, where each multiple edge has at most one bend; and

(iii) Such a drawing in (i) and (ii) can be constructed in linear time.

We see that (ii) follows from (i) by subdividing each multiple directed edge (u, v) into a directed path (u, w, v) with a new vertex w to obtain a simple st-planar graph. Figure 1(b) illustrates an example of an st-planar graph.

3 Path-Monotonic Upward Drawing

When a plane graph $\gamma$ has a pair of multiple edges e and $e'$ that encloses no vertex in the interior, we can ignore one of these edges (say $e'$) to find an upward drawing of $\gamma$, because we can draw $e'$ along the drawing of e in any upward drawing of the resulting plane graph. In what follows, we assume that a given plane graph is pseudo-simple.

We say that two paths P and $P'$ in a plane graph $\gamma$ are 1-independent if they intersect at a common internal vertex and have no other common vertex; or they have no common vertex that is an internal vertex of one of them (where they may share at most two vertices that are end-vertices to both paths). We call a set $\mathcal {P}$ of paths in $\gamma$ 1-independent if any two paths in $\mathcal {P}$ are 1-independent.

In this paper, we present a sufficient condition for an instance $(\gamma , \mathcal {P})$ to admit an (s, t)-upward drawing of $\gamma$ that is monotonic to $\mathcal {P}$ for any two outer vertices $s,t\not \in V_{\mathrm {inl}}(\mathcal {P})$. We also present a linear-time algorithm to construct such a drawing. The main contribution of this paper is summarized in the following main theorem.

Theorem 1

Let $\gamma =(G=(V,E),F)$ be a pseudo-simple connected plane graph and $\mathcal {P}$ be a set of paths of length at least 2 in G, where $V_{\mathrm {inl}}$ denotes the set of internal vertices in paths in $\mathcal {P}$. If the following conditions hold, then any pair of outer vertices $s, t\not \in V_{\mathrm {inl}}$ admits an (s, t)-upward (straight-line, if $\gamma$ is simple) drawing D monotonic to $\mathcal {P}$, which can be computed in linear time:

(i) $\mathcal {P}$ is 1-independent; and

(ii) There is no pair of a path $P\in \mathcal {P}$ and a cycle K with $|V(K)\setminus V_{\mathrm {inl}}|\le 1$ such that K encloses an end-vertex of P and the internal vertices of P and the vertices in $V(K)\cap V_{\mathrm {inl}}$ belong to the same component of the subgraph $G[V_{\mathrm {inl}}]$ induced from G by $V_{\mathrm {inl}}$.

We assume that the boundary of $\gamma$ forms a cycle $C^o$ such that $V(C^o)\cap V_{\mathrm {inl}}=\emptyset$; if necessary, add two new outer edges $e_{s,t}$ and $e'_{s,t}$ joining the two outer vertices s and t to form a new outer facial cycle $C^o$ of length 2. In what follows, we assume that the boundary of a given connected planar graph $\gamma$ forms a cycle.

We prove Theorem 1 by showing that every instance satisfying the conditions of the theorem admits an (s, t)-orientation compatible to $\mathcal {P}$, which implies that the instance admits an (s, t)-upward straight-line (resp., poly-line) drawing monotonic to $\mathcal {P}$ by Lemma 2. To prove the existence of such an (s, t)-orientation compatible to $\mathcal {P}$, we show that Theorem 1 is reduced to the following case.

Lemma 3

Let $\gamma =(G=(V,E),F)$ be a pseudo-simple connected plane graph and $\mathcal {P}$ be a set of paths of length at least 2 in G, where $V_{\mathrm {inl}}$ denotes the set of internal vertices in paths in $\mathcal {P}$. If the following conditions hold, then any pair of outer vertices $s, t\not \in V_{\mathrm {inl}}$ admits an (s, t)-orientation $\widetilde{\gamma }$ of $\gamma$ compatible to $\mathcal {P}$, which can be computed in linear time:

(i) $\mathcal {P}$ is 1-independent; and

(ii) For the set $\{V_i\subseteq V_{\mathrm {inl}}\mid i=1,2,\ldots ,p\}$ of components in $G[V_{\mathrm {inl}}]$ and the partition $\{\mathcal {P}_i\mid i=1,2,\ldots ,p\}$ of $\mathcal {P}$ such that $V_{\mathrm {inl}}(\mathcal {P}_i)\subseteq V_i$, there exists an inclusive set $\mathcal {C}=\{C_1,C_2,\ldots ,C_p\}$ of edge-disjoint cycles such that, for each $i=1,2,\ldots ,p$, $V_i\subseteq V_{\mathrm {enc}}(C_i;\gamma )$ and $V_{\mathrm {end}}(\mathcal {P}_i)\subseteq V(C_i)\subseteq V\setminus V_{\mathrm {inl}}$.

The instance in Fig. 1(a) has three components $V_1=\{u_1,u_2\}$, $V_2=\{u_3,u_4,\,u_5,u_6\}$ and $V_3=\{u_7\}$ in $G[V_{\mathrm {inl}}]$. The instance admits a cycle set $\mathcal {C}=\{C_1=(v_1,v_2,w_4,v_3,v_4,$ $v_5,v_6), C_2=(v_3,v_7,v_8,v_9,w_5,v_{10},$ $v_{11},w_6),$ $C_3=(v_{10},v_{12},v_{13},v_{14})\}$, which satisfies the condition of Lemma 3. Figure 1(b) illustrates an (s, t)-orientation $\widetilde{\gamma }$ of $\gamma$ in Fig. 1(a) that is compatible to $\mathcal {P}$.

We prove in Sect. 5 that a given instance of Theorem 1 can be augmented to a plane graph so that the condition of Lemma 3 is satisfied.

4 Bipolar Orientation on Plane Graphs

This section presents several properties on bipolar orientations in plane graphs, which will be the basis to our proof of Lemma 3. Let $g:V\rightarrow \mathbb {R}$ be a vertex-weight function in a graph $G=(V,E)$, where $\mathbb {R}$ denote the set of real numbers. We say that g is bipolar (or (a, b)-bipolar) to a subgraph $G'=(V',E')$ of G if (i) $g(u)\ne g(v)$ for the end-vertices u and v of each edge $e=uv\in E'$; (ii) $V'$ contains a vertex pair (a, b) such that $g(a)<g(v)<g(b)$ for all vertices $v\in V'\setminus \{a,b\}$; and (iii) each vertex $v\in V'\setminus \{a,b\}$ has a neighbor $u\in N_{G'}(v)$ with $g(u)<g(v)$ and a neighbor $w\in N_{G'}(v)$ with $g(v)<g(w)$.

Observe that an (a, b)-bipolar function g to a graph G is essentially equivalent to an st-numbering of G in the sense that it admits an st-numbering $\sigma :V(G)\rightarrow \{1,2,\ldots ,|V(G)|\}$ of G such that $\sigma (a)=1$, $\sigma (b)=|V(G)|$ and $\sigma (u)<\sigma (v)$ holds for any pair of vertices $u,v\in V$ with $g(u)<g(v)$. We observe that any bipolar function in a plane graph is bipolar to every cycle in the next lemma.

Lemma 4

For a biconnected graph $G=(V,E)$, let $g:V\rightarrow \mathbb {R}$ be a function (s, t)-bipolar to G. If G admits a plane graph $\gamma =(V,E,F)$, then the boundary of each face $f\in F$ forms a cycle $C_f$ and g is bipolar to $C_f$.

The next lemma states that a bipolar orientation of a plane graph can be obtained from bipolar orientations of the interior and exterior subgraphs of a cycle.

Lemma 5

For a biconnected plane graph $\gamma =(V,E,F)$ and a cycle C of the graph (V, E), let $\gamma _{C}$ (resp., $\gamma _{\overline{C}})$ denote the interior (resp., exterior) subgraph of $\gamma$ by C. For two outer vertices s and t of $\gamma$, let $\widetilde{\gamma _C}$ be an (s, t)-orientation of $\gamma _{C}$. Then the orientation $\widetilde{C}$ restricted from $\widetilde{\gamma _C}$ to C is an (a, b)-orientation of C for some $a,b\in V(C)$, and for any (a, b)-orientation $\widetilde{\gamma _{\overline{C}}}$ of $\gamma _{\overline{C}}$, the orientation $\widetilde{\gamma }$ of $\gamma$ obtained by combining $\widetilde{\gamma _C}$ and $\widetilde{\gamma _{\overline{C}}}$ is an (s, t)-orientation of $\gamma$.

Fig. 2.

(a) mesh graph $\eta _2=(C_2,\mathrm {P}_2)$ induced from the instance $\gamma$ in Fig. 1(a) with cycle $C_2$; an instance satisfying the condition of Lemma 3: (b) $(s_2=v_{11}, t_2=v_8)$-orientation $\widetilde{\sigma (\mu _2)}$ of the split mesh graph $\sigma (\mu _2)$; (c) sun augmentation $\gamma ^*$.

We now examine a special type of instances of Lemma 3.

Mesh Graph. A mesh graph is defined to be a pair $\mu =(\gamma ,\mathcal {P})$ of a biconnected plane graph $\gamma =(V,E,F)$ and a 1-independent set $\mathcal {P}$ of paths in the graph (V, E) such that (i) $\gamma$ consists of an outer facial cycle C and the paths in $\mathcal {P}$; and (ii) each path $P\in \mathcal {P}$ ends with vertices in C and has no internal vertex from C, where $V=V(C)\cup \bigcup _{P\in \mathcal {P}}V(P)$ and $E=E(C)\cup \bigcup _{P\in \mathcal {P}}E(P)$. We may denote a mesh graph $(\gamma ,\mathcal {P})$ with an outer facial cycle C by $\mu =(C,\mathcal {P})$. Figure 2(a) illustrates an example of a mesh graph.

Let $\mu =(\gamma =(V,E,F),\mathcal {P})$ be a mesh graph with an outer facial cycle C. To find an orientation of $\mu$ compatible to $\mathcal {P}$, we treat each u, v-path $P\in \mathcal {P}$ as a single edge $e_P=uv$, which we call the split edge of P. The split mesh graph is defined to be the graph $\sigma (\mu )$ obtained from $\mu$ by replacing each path $P\in \mathcal {P}$ with the split edge $e_P$; i.e., $\sigma (\mu )=(V(C), E(C)\cup \{e_P\mid P\in \mathcal {P}\} )$.

Let $\widetilde{\sigma (\mu )}$ be an orientation of the split mesh graph $\sigma (\mu )$. We say that $\widetilde{\sigma (\mu )}$ induces an orientation $\widetilde{\mu }$ of $\mu$ if each u, v-path $P\in \mathcal {P}$ is directed from u to v in $\widetilde{\mu }$ when $e_P$ is a directed edge (u, v) in $\widetilde{\sigma (\mu )}$. Clearly $\widetilde{\mu }$ is compatible to $\mathcal {P}$. Figure 2(b) illustrates an (s, t)-orientation of the split mesh graph.

The next lemma states that an (s, t)-orientation of a mesh graph compatible to $\mathcal {P}$ can be obtained by computing an (s, t)-orientation of the split mesh graph.

Lemma 6

For a mesh graph $\mu$ and an (s, t)-orientation $\widetilde{\sigma (\mu )}$ of the split mesh graph $\sigma (\mu )$, the orientation $\widetilde{\mu }$ of $\mu$ induced by $\widetilde{\sigma (\mu )}$ is an (s, t)-orientation of $\mu$.

5 Coating and Confiner

To prove that Theorem 1 implies Lemma 3, this section gives a characterization of a plane graph that can be augmented to a plane graph such that specified vertices are contained in some cycles. Let $\gamma =(G=(V,E),F)$ be a plane graph.

We call an inclusive set $\mathcal {C}=\{C_1,C_2,\ldots ,C_p\}$ of edge-disjoint cycles in $\gamma$ a coating of a family $\mathcal {X}=\{X_1,X_2,\ldots ,X_p\}$ of subsets of V if for each $i=1,2,\ldots ,p$, $V(C_i)\cap X=\emptyset$ and $V_{\mathrm {enc}}(C_i;\gamma )\supseteq X_i$. We say that a coating $\mathcal {C}=\{C_1,C_2,\ldots ,C_p\}$ of $\mathcal {X}$ covers a given family $\{Y_1,Y_2,\ldots ,Y_p\}$ of vertices if $V(C_i)\supseteq Y_i$ for each $i=1,2,\ldots ,p$.

For disjoint subsets $S,T\subseteq V$ in $\gamma$ such that the subgraph G[S] induced by S is connected, we call a cycle K of G an (S, T)-confiner if $|V(K)\setminus S|\le 1$ and the interior vertex set $V_{\mathrm {enc}}(K;\gamma )$ of K contains some vertex $t\in T$.

A plane augmentation of a plane graph $\gamma =(V,E,F)$ is defined to be a plane embedding $\gamma ^*=(V^*,E^*,F^*)$ of a supergraph $(V^*,E^*)$ of (V, E) such that the embedding obtained from $\gamma ^*$ by removing the additional vertices in $V^*\setminus V$ and edges in $E^*\setminus E$ is equal to the original embedding $\gamma$.

Sun Augmentation. Let $\gamma =(V,E,F)$ be a pseudo-simple connected plane graph such that the outer boundary is a cycle. We introduce sun augmentation, a method of augmenting $\gamma$ into a pseudo-simple biconnected plane graph by adding new vertices and edges in the interior of some inner faces of $\gamma$.

For an inner face $f\in F$, let $W_f=(v_1,v_2,\ldots ,v_p)$ denote the sequence of vertices that appear along the boundary in the clockwise order, where $p\ge 3$ since $\gamma$ is pseudo-simple. For each inner face $f\in F$:

• (i) create a new cycle $C^*_f=(v'_1,v'_2,\ldots ,v'_p)$ with p new vertices $v'_i$, $i=1,2,\ldots ,p$ in the interior of f so that the facial cycle of f encloses $C^*_f$; and

• (ii) join each vertex $v_i$, $i=1,2,\ldots ,p$ with $v'_i$ and $v'_{i+1}$ with new edges $e'_i=v_i v'_i$ and $e''_i=v_i v'_{i+1}$, where we regard $v'_{p+1}$ as $v'_1$; We call the new face whose set consists of the p new edges $e'_i$, $i=1,2,\ldots ,p$ a core face and call a vertex along a core face a core vertex.

Figure 2(c) illustrates how the sun augmentation $\gamma ^*$ is constructed.

The next lemma characterizes when a plane graph with two vertex subsets X and Y can be augmented such that a set of cycles contains vertices in Y without visiting any vertex in X.

Lemma 7

For a pseudo-simple connected plane graph $\gamma =(G=(V,E),F)$ such that the boundary forms a cycle $C^o$ and a subset $X \subseteq V\setminus V(C^o)$, let $\{X_i\subseteq X\mid i=1,2,\ldots ,p\}$ denote the set of components in G[X] and $Y_i\subseteq N_G(X_i)$, $i=1,2,\ldots ,p$ be subsets of V, where possibly $Y_i\cap Y_j\ne \emptyset$ for some $i\ne j$.

Then $\gamma$ contains no $(X_i,Y_i)$-confiner for any $i=1,2,\ldots ,p$ if and only if the sun augmentation $\gamma ^*=(V^*,E^*,F^*)$ of $\gamma$ contains a coating $\mathcal {C}$ of $\{X_1,X_2,\ldots ,X_p\}$ that covers $\{Y_1,Y_2,\ldots ,Y_p\}$. Moreover the following can be computed in linear time: (i) Testing whether $\gamma$ contains an $(X_i,Y_i)$-confiner for some $i=1,2,\ldots ,p$; and (ii) Finding a coating $\mathcal {C}$ of $\{X_1,X_2,\ldots ,X_p\}$ that covers $\{Y_1,Y_2,\ldots ,Y_p\}$ in $\gamma ^*$ when $\gamma$ contains no $(X_i,Y_i)$-confiner for any $i=1,2,\ldots ,p$.

We show how the assumption in Lemma 3 is derived from the assumption of Theorem 1 using Lemma 7. Let $\{V_i\subseteq V_{\mathrm {inl}}\mid i=1,2,\ldots ,p\}$ denote the set of components in $G[V_{\mathrm {inl}}]$ and $\mathcal {P}_i$, $i=1,2,\ldots ,p$ denote the partition of $\mathcal {P}$ such that $V_{\mathrm {inl}}(\mathcal {P}_i)\subseteq V_i$. We apply Lemma 7 to the plane graph $\gamma$ in Theorem 1 by setting $X:=V_{\mathrm {inl}}$, $X_i:=V_i$ and $Y_i:=V_{\mathrm {end}}(\mathcal {P}_i)$, $i=1,2,\ldots ,p$. Note that $X\subseteq V\setminus V(C^o)$. We show from the assumption in Theorem 1 that $\gamma$ has no $(X_i,Y_i)$-confiner for any $i=1,2,\ldots ,p$.

To derive a contradiction, assume that $\gamma$ has an $(X_i,Y_i)$-confiner K for some $i\in \{1,2,\ldots ,p\}$, where $V_{\mathrm {enc}}(K;\gamma )$ of K contains an end-vertex $y\in Y_i=V_{\mathrm {end}}(\mathcal {P}_i)$ of some path $P\in \mathcal {P}_i$. Since $|K|\ge 2$ and $|K\setminus X_i|\le 1$, K contains a vertex $v\in K\cap X_i$. Now vertex v and the internal vertices of P belong to the same component $G[X_i]=G[V_i]$ of G[X] in $\gamma$. This contradicts the assumption in Theorem 1. Hence the condition of Lemma 7 holds and the sun augmentation $\gamma ^*$ of $\gamma$ admits a coating $\mathcal {C}=\{C_1,C_2,\ldots ,C_p\}$ of $\{X_i=V_i\mid i=1,2,\ldots ,p\}$ that covers $\{Y_i=V_{\mathrm {end}}(\mathcal {P}_i)\mid i=1,2,\ldots ,p\}$. We see that such a set $\mathcal {C}$ of cycles satisfies the condition of Lemma 3.

6 Algorithmic Proof

This section presents an algorithmic proof to Lemma 3.

For a pseudo-simple biconnected plane graph $\gamma =(V,E,F)$ and a 1-independent set $\mathcal {P}$ of paths of length at least 2, we are given a partition $\{\mathcal {P}_i\mid i=1,2,\ldots ,p\}$ of $\mathcal {P}$ and an inclusive set $\mathcal {C}=\{C_1,C_2,\ldots ,C_p\}$ of edge-disjoint cycles that satisfy the condition of Lemma 3. For the instance $(\gamma ,\mathcal {P},\mathcal {C})$ in Fig. 1(a), we obtain $\mathcal {P}_1=\{P_1,P_2,P_3\}$, $\mathcal {P}_2=\{P_4,P_5,P_6,P_7\}$, $\mathcal {P}_3=\{P_8,P_9\}$ and $\mathcal {C}=\{C_1=(v_1,v_2,w_4,v_3,v_4,v_5,v_6), C_2=(v_3,v_7,v_8,v_9,w_5,v_{10},v_{11},w_6), C_3=(v_{10},v_{12},v_{13},v_{14})\}$.

Let $\mathcal {I}=(\mathcal {C},\mathcal{E})$ denote the inclusion-forest of $\mathcal {C}$, and $\mathrm {Ch}(C)$ denote the set of child cycles $C'$ of each cycle $C\in \mathcal {C}$ in $\mathcal {I}$, where the cycle C is called the parent cycle of each cycle $C'\in \mathrm {Ch}(C)$. We call a cycle $C\in \mathcal {C}$ that has no parent cycle a root cycle in $\mathcal {C}$, and let $\mathcal {C}_{\mathrm {rt}}$ denote the set of root cycles in $\mathcal {C}$. For a notational simplicity, we assume that the indexing of $C_1,C_2,\ldots ,C_p$ satisfies $i<j$ when $C_i$ is the parent cycle of $C_j$.

Based on the inclusion-forest $\mathcal {I}$, we first decompose the entire plane graph $\gamma$ into plane subgraphs $\gamma _i$, $i=0,1,\ldots ,p$ as follows. Define $\gamma _0$ to be the plane graph $\gamma - \cup _{C\in \mathcal {C}_{\mathrm {rt}}}(V_{\mathrm {enc}}(C;\gamma )\cup E_{\mathrm {enc}}(C;\gamma ))$ obtained from $\gamma$ by removing the vertices and edges in the interior of root cycles $C\in \mathcal {C}_{\mathrm {rt}}$. For each $i=1,2,\ldots ,p$, define $\gamma _i$ to be the plane graph $\gamma [C_i]_{\mathrm {enc}}- \cup _{C\in \mathrm {Ch}(C_i)}(V_{\mathrm {enc}}(C;\gamma )\cup E_{\mathrm {enc}}(C;\gamma ))$ obtained from the interior subgraph $\gamma [C_i]_{\mathrm {enc}}$ by removing the vertices and edges in the interior of child cycles C of $C_i$.

For each cycle $C_i$, $i=1,2,\ldots ,p$, we consider the mesh graph $\mu _i=(C_i,\mathcal {P}_i)$, where $\mu _i$ is a plane subgraph of $\gamma _i$. For each inner face f of $\mu _i$, we consider the interior subgraph $\gamma _i[C_f]_{\mathrm {enc}}$ of the facial cycle $C_f$ of f in $\gamma _i$, where we call an inner face f of $\mu _i$ trivial if $C_f$ encloses nothing in $\gamma _i$; i.e., $V_{\mathrm {enc}}(C_f;\gamma _i)\cup E_{\mathrm {enc}}(C_f;\gamma _i)=\emptyset$. Let $F(\mu _i)$ denote the set of non-trivial inner faces f of $\mu _i$.

We determine orientations of subgraphs $\gamma _i$ by an induction on $i=0,1,\ldots ,p$. For specified outer vertices $s,t\in V(C^o)\setminus V_{\mathrm {inl}}$, compute an (s, t)-orientation $\widetilde{\gamma _0}$ of $\gamma _0$ using Lemma 1. Consider the plane subgraph $\gamma _{i}$ with $i\ge 1$, where we assume that a bipolar orientation $\widetilde{\gamma _j}$ of $\gamma _j$ has been obtained for all $j< i$. Let k denote the index of the parent cycle $C_k$ of $C_i$ or $k=0$ if $C_i$ is a root cycle, where a bipolar orientation $\widetilde{\gamma _k}$ of $\gamma _k$ has been obtained. In $\widetilde{\gamma _k}$, cycle $C_i$ forms an inner facial cycle and the orientation restricted to the facial cycle $C_i$ is a bipolar orientation, which is an $(s_i,t_i)$-orientation $\widetilde{C_i}$ for some vertices $s_i,t_i\in V(C_i)$ by Lemma 4. We determine an $(s_i,t_i)$-orientation of $\gamma _i$ as follows:

Step (a): Compute an $(s_i,t_i)$-orientation $\widetilde{\mu }_i$ of the mesh graph $\mu _i=(C_i,\mathcal {P}_i)$;

Step (b): Extend the orientation $\widetilde{\mu }_i$ to the interior subgraph $\gamma _i[C_f]_{\mathrm {enc}}$ of each non-trivial inner face $f\in F(\mu _i)$.

At Step (a), we compute an $(s_i,t_i)$-orientation $\widetilde{\sigma (\mu _i)}$ of the split mesh graph $\sigma (\mu _i)$ to obtain an $(s_i,t_i)$-orientation $\widetilde{\mu }_i$ using Lemma 6. For Step (b), we observe that orientation $\widetilde{\mu }_i$ is $(s_f,t_f)$-bipolar to the facial cycle $C_f$ of f for some vertices $s_f,t_f\in V(C_f)$ by Lemma 4. We compute an $(s_f,t_f)$-orientation $\widetilde{\gamma _i[C_f]_{\mathrm {enc}}}$ of the interior subgraph $\gamma _i[C_f]_{\mathrm {enc}}$ induced from $\gamma _i$ by $C_f$ using Lemma 1. An $(s_i,t_i)$-orientation of $\gamma _i$ is obtained from the $(s_i,t_i)$-orientation $\widetilde{\mu }_i$ and $(s_f,t_f)$-orientations $\widetilde{\gamma _i[C_f]_{\mathrm {enc}}}$ for all inner faces $f\in F(\mu _i)$.

We repeat the above procedure until $i=p$. Finally construct an orientation $\widetilde{\gamma }$ of $\gamma$ by combining bipolar orientations $\widetilde{\gamma }_i$ of $\gamma _i$, $i=0,1,\ldots ,p$. By Lemma 5, $\widetilde{\gamma }$ is an (s, t)-orientation, which is compatible to $\mathcal {P}$ by the construction of $\widetilde{\gamma }$. This proves the correctness of our algorithm for computing an (s, t)-orientation $\widetilde{\gamma }$ compatible to $\mathcal {P}$.

Fig. 3.

(a) An $(s=v_5,t=v_7)$-orientation $\widetilde{\gamma }_0$ of $\gamma _0$; (b) Mesh graph $\mu _1=(C_1,\mathcal {P}_1)$, where $C_1$ is directed as an $(s_1=v_5, t_1=v_1)$-orientation; (c) Mesh graph $\mu _2=(C_2,\mathcal {P}_2)$, where $C_2$ is directed as an $(s_2=v_{11}, t_2=v_8)$-orientation; (d) Subgraph $\gamma _1$ with an $(s_1, t_1)$-orientation $\widetilde{\mu }_1$ of $\mu _1$; (e) Subgraph $\gamma _2$ with an $(s_2, t_2)$-orientation $\widetilde{\mu }_2$ of $\mu _2$; (f) Mesh graph $\mu _3=(C_3,\mathcal {P}_3)$, where $C_3$ is directed as an $(s_3=v_{10}, t_3=v_{13})$-orientation; (e) Subgraph $\gamma _3$ with an $(s_3, t_3)$-orientation $\widetilde{\mu }_3$ of $\mu _3$.

The inclusion-forest of an inclusive set $\mathcal {C}$ of edge-disjoint cycles can be constructed in linear time  [11]. Constructing all plane subgraphs $\gamma _i$ and face sets $F(\mu _i)$, $i=1,2,\ldots ,p$ can be done in linear time, since we can find them such that each edge in $\gamma$ is scanned a constant number of times. We see that a bipolar orientation of mesh graph $\mu _i$ or subgraph $\gamma _i$ can be computed in time linear to the size of the graph by Lemmas 1 and 6. The total size of these graphs $\mu _i$, $i=1,2,\ldots ,p$ and $\gamma _i$, $i=0,1,\ldots ,p$ is bounded by the size of input graph $\gamma$. Therefore the algorithm can be executed in linear time. This proves Lemma 3.

Figure 3 shows an execution of the algorithm applied to the instance $(\gamma ,\mathcal {P},\mathcal {C})$ in Fig. 1(a). Figures 3(b), (c) and (f) show mesh graphs $\mu _1$, $\mu _2$ and $\mu _3$, respectively for the instance in Fig. 1(a), where $\mathcal {C}_{\mathrm {rt}}=\{C_1,C_2\}$, $\mathrm {Ch}(C_1)=\emptyset$, $\mathrm {Ch}(C_2)=\{C_3\}$, $F(\mu _1)=\{f_1\}$ $(C_{f_1}=(v_5,u_1,v_2,w_4,v_3,u_2,v_4))$, $F(\mu _2)=\{f_2,f_3\}$ $(C_{f_2}=(v_{10},u_5,u_4, u_6)$, $C_{f_3}=(v_{10},u_6,u_4, v_9,w_5))$, $F(\mu _3)=\{f_4\}$ $(C_{f_4}=(v_{12}, v_{13}, v_{14}))$. Figures 3(a), (d), (e) and (g) show subgraphs $\gamma _0$, $\gamma _1$, $\gamma _2$ and $\gamma _3$, respectively for the instance in Fig. 1(a). Figure 1(b) shows an (s, t)-orientation of the instance $\gamma$ in Fig. 1(a).

7 Upward Drawing of a Non-planar Embedding

Let $\varGamma$ be a non-planar embedding of a graph G, and $E^*$ denote the set of crossing edges. We define a crossing-set to be a maximal subset $E'\subseteq E^*$ such that every two edges $e,e'\in E'$ admit a sequence of edges $e_1,e_2,\ldots ,e_p$, where $e_1=e$, $e_p=e'$ and edges $e_i$ and $e_{i+1}$ cross for each $i=1,2,\ldots ,p-1$. Observe that $E^*$ is partitioned into disjoint crossing-sets $E^*_1,E^*_2,\ldots ,E^*_p$.

Let $E^*_i$ be a crossing-set, and $\varGamma [E^*_i]$ denote the plane graph induced from $\varGamma$ by the edges in $E^*_i$, where $\varGamma [E^*_i]$ is connected. We call $E^*_i$ outer if the end-vertices of edges in $E^*_i$ appear as outer vertices along the boundary of $\varGamma [E^*_i]$.

We apply Lemma 3 to the problem of finding an upward drawing of a non-planar embedding of a graph, and prove the following results.

Theorem 2

Let $\varGamma$ be a non-planar embedding of a graph G such that each crossing-set is outer, and let $n_{\mathrm {c}}$ denote the number of crossings in $\varGamma$. Then for any pair of outer vertices s and t in $\varGamma$, there is an (s, t)-upward drawing of $\varGamma$, and an upward poly-line drawing of $\varGamma$ with $O(n+n_{\mathrm {c}})$ bends can be constructed in $O(n+n_{\mathrm {c}})$ time and space, where $n=|V(G)|$.

Thomassen  [17] showed that there are two forbidden subgraphs for a 1-plane graph (i.e., graph can be embedded at most one crossing per edge) to admit a straight-line drawing. Theorem 2 implies the following.

Corollary 1

Every 1-plane graph admits an (s, t)-upward poly-line drawing for any outer vertices s and t, where each edge has at most one bend. Such a drawing can be constructed in linear time.