# A Characterization of Horoidal Digraphs

Ardeshir Dolati

► To cite this version:

Ardeshir Dolati. A Characterization of Horoidal Digraphs. 2nd International Conference on Topics in Theoretical Computer Science (TTCS), Sep 2017, Tehran, Iran. pp.11-25, 10.1007/978-3-319-68953-1_2. hal-01760640

HAL Id: hal-01760640

https://inria.hal.science/hal-01760640

Submitted on 6 Apr 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Characterization of Horoidal Digraphs

Ardeshir Dolati

Department of Computer Science, Shahed University
PoBox 18151-159, Tehran, Iran
dolati@shahed.ac.ir

**Abstract.** In this paper we investigate the upward embedding problem on the horizontal torus. The digraphs that admit upward embedding on this surface are called *horoidal digraphs*. We shall characterize the horoidal digraphs, combinatorially. Then, we construct a new digraph from an arbitrary digraph in such a way that the new digraph has an upward embedding on sphere if and only if it is horoidal. By using these constructed digraphs, we show that the decision problem whether a di-graph has an upward embedding on the horizontal torus is NP-Complete.

*Keywords:* upward embedding, sphericity testing, horizontal torus, computational complexity, horoidal st-graphs

## 1 Introduction

We call a digraph *horoidal* if it has an upward drawing with no edge crossing on the *horizontal torus*; an embedding of its underlying graph so that all directed edges are monotonic and point to the direction of *z*-axis. Throughout this paper, by surfaces we mean two-dimensional compact orientable surfaces such as sphere, torus and connected sum of tori with a fixed embedding in three-dimensional space $\mathbb{R}^3$. In this paper we deal with upward drawing with no edge crossing (hereafter it will be referred as *upward embedding*) on a special embedding of the ring torus in $\mathbb{R}^3$ which we call the horizontal torus. This surface is denoted by $T_h$.

There are major differences between graph embedding and upward embedding of digraphs. Despite the fact that the vertical torus and the horizontal torus are two special embeddings of the ring torus in three-dimensional space $\mathbb{R}^3$, and are topologically equivalent, Dolati, Hashemi and Khosravani [11] have shown that a digraph with the underlying graph with genus one, may have an upward embedding on the vertical torus, and may fail to have an upward embedding on the horizontal torus. In addition, while Filotti, Miller and Reif [12] have shown that the question whether an undirected graph has an embedding on a fixed surface has polynomial time algorithm, the decision problem of upward embedding testing is NP-complete, even on sphere and plane. In the following we review the results on upward embedding from the characterization and computational complexity point of view.
**1.1 Plane**

A digraph is called *upward planar* if it has an upward embedding on the plane.

**Characterization** An st-digraph is a single source and single sink digraph in which there is an arc from the source to the sink. Di Battista and Tamassia [7] and Kelly [19], independently, characterized the upward planarity of digraphs.

**Theorem 1.1** (*Di Battista and Tamassia [7], Kelly [19]*) A digraph is upward planar if and only if it is a spanning subgraph of an st-digraph with planar underlying graph.

**Testing** The decision problem associated with plane is stated as follows.

**Problem 1** *Upward embedding testing on plane (Upward planarity testing)*

**INSTANCE:** Given a digraph *D*.

**QUESTION:** Does *D* have an upward embedding on plane?

This decision problem has polynomial time algorithms for some special cases; Bertolazzi, Di Battista, Liotta, and Mannino [5] have given a polynomial-time algorithm for testing the upward planarity of three connected digraphs. Thomassen [21] has characterized upward planarity of the single source digraphs in terms of forbidden circuits. By combining Thomassen's characterization with a decomposition scheme Hutton and Lubiw [18] have given a polynomial-time algorithm to test if a single source digraph with *n* vertices is upward planar in *O*(n²). Bertolazzi, Di Battista, Mannino, and Tamassia [6] have presented an optimal algorithm to test whether a single source digraph is upward planar in the linear time. Papakostas [20] has given a polynomial-time algorithm for upward planarity testing of outerplanar digraphs.

The results for the general case is stated in the following theorem.

**Theorem 1.2** (*Garg, Tamassia [13, 14], Hashemi, Rival, Kisielewicz [17]*) *Upward planarity testing is NP-Complete.*

**1.2 Round sphere**

A digraph is called *spherical* if it has an upward embedding on the sphere.

**Characterization** The following theorem characterizes the sphericity of digraphs.

**Theorem 1.3** (*Hashemi, Rival, Kisielewicz [15, 17]*) A digraph is spherical if and only if it is a spanning subgraph of a single source and single sink digraph with planar underlying graph.
**Testing** The decision problem associated with this surface is as follows.

**Problem 2** *Upward embedding testing on sphere (Upward sphericity testing)*

**INSTANCE:** Given a digraph *D*.

**QUESTION:** Does *D* have an upward embedding on the round sphere?

Dolati and Hashemi [10] have presented a polynomial-time algorithm for upward sphericity testing of the embedded single source digraphs. Recently, Dolati [9] has presented an optimal linear algorithm for upward sphericity testing of this class of digraphs.

The results of the general case is stated in the following theorem.

**Theorem 1.4** (Hashemi, Rival, Kisielewicz [17]) *Upward sphericity testing is NP-Complete.*

## 1.3 Horizontal torus

Another surface to be mentioned is horizontal torus. Here we recall its definition. The surface obtained by the revolving of the curve $c: (y-2)^2+(z-1)^2 = 1$ round the line $L: y=0$ as its axis of the revolution in the $yz$-plane. In this case the part of $T_h$ resulting from the revolving of that part of $c$ in which $y \le 2$ is called *inner layer*. The other part of $T_h$ resulting from the revolving of that part of $c$ in which $y \ge 2$ is called *outer layer*. The curves generating from revolving points $(0, 2, 0)$ and $(0, 2, 2)$ round the axis of revolution are minimum and maximum of the torus and are denoted by $c_{min}$ and $c_{max}$, respectively. According to our definition, it is clearly seen that $c_{min}$ and $c_{max}$ are common between the inner layer and the outer layer. Our main results bear characterization of the digraphs that have upward embedding on the horizontal torus; we call them the horoidal digraphs. Note that, this characterization can not be applied for vertical torus. Because the set of all digraphs that admit upward embedding on horizontal torus is a proper subset of the set of all digraphs that have upward embedding on vertical torus.

**Characterization** In the next section we will characterize the horoidal digraphs. Let $D$ be a horoidal digraph that is not spherical. As we will show, in the new characterization, a proper partition of the arcs into two parts will be presented. This partition must be constructed in such a way that the induced subdigraph on each part is spherical. Moreover, the common sources and the common sinks of the two induced subgraphs must be able to be properly identified. Note that, the arcs set of one of these parts can be considered as $\emptyset$. Therefore, the set of spherical digraphs is a proper subset of the set of horoidal digraphs.

**Testing** It has been shown that the following corresponding decision problem is not easy [8]. We will investigate its complexity in details in the next sections.
**Problem 3** *Upward embedding testing on $T_h$*

**INSTANCE:** Given a digraph *D*.

**QUESTION:** Does *D* have an upward embedding on the horizontal torus $T_h$?

Dolati, Hashemi, and Khosravani [11] have presented a polynomial-time algorithm to decide whether a single source and single sink digraph has an upward embedding on $T_h$. In this paper, by using a reduction from the sphericity testing decision problem, we show that this decision problem is NP-Complete.

Recently, Auer et al. in [1-4] consider the problem by using the fundamental polygon of the surfaces. They use a vector field for defining the direction of the arcs. By their definition, acyclicity condition is not a necessary condition for a digraph to have upward embedding.

The rest of this paper is organized as follows. After some preliminaries in Section 2 we present a characterization of a digraph to have an upward embedding on $T_h$ in Section 3. Then we show that the decision problem to decide whether a digraph has an upward embedding on the horizontal torus belongs to NP. In section 4 we shall present a polynomial reduction from the sphericity decision problem to the upward embedding testing on $T_h$. In Section 5 we present conclusions and some related open problems.

## 2 Preliminaries

Here, we introduce some definitions and notations which we use throughout the paper. By a digraph $D$ we mean a pair $D = (V, A)$ of vertices $V$, and arcs $A$. In this paper all digraphs are finite and simple (without loops and multiple edges). A necessary condition for a digraph to have an upward embedding on a surface is that it has no directed cycle, i.e. it is acyclic. For any two vertices $u$ and $v$ of a digraph $D$, the symbol $(u, v)$ denotes an arc in $D$ that originates from $u$ and terminates at $v$. A *source* of $D$ is a vertex with no incoming arcs. A *sink* of $D$ is a vertex with no outgoing arcs. An *internal* vertex of $D$ has both incoming and outgoing arcs. Let $x$ be a vertex of $D$, by $\text{od}(x)$ we mean the number of the outgoing arcs of $x$ and by $\text{id}(x)$ we mean the number of the incoming arcs to $x$. A *directed path* of a digraph $D$ is a list $v_0, a_1, v_1, \dots, a_k, v_k$ of vertices and arcs such that, for $1 \le i \le k$; $a_i = (v_{i-1}, v_i)$. An *undirected path* of a digraph $D$ is a list $v_0, a_1, v_1, \dots, a_k, v_k$ of vertices and arcs such that, for $1 \le i \le k$; $a_i = (v_{i-1}, v_i)$ or $a_i = (v_i, v_{i-1})$. If $D$ is a digraph, then its *underlying graph* is the graph obtained by replacing each arc of $D$ by an (undirected) edge joining the same pair of vertices. A digraph $D$ is *weakly connected* or simply *connected* if, for each pair of vertices $u$ and $v$, there is a *undirected path* in $D$ between $u$ and $v$. We use of the following equivalence relation $\mathbf{R}$ on the arcs of a digraph, introduced by Dolati et. al in [11].

**Definition 2.5** *Given a digraph $D = (V, A)$. We say two arcs $a, a' \in A(D)$ are in relation $\mathbf{R}$ if they belong to a directed path or there is a sequence $P_1, P_2, \dots, P_k$, for some $k \ge 2$, of directed paths with the following properties:*

$$ (i) \ a \in P_1 \text{ and } a' \in P_k. $$
(ii) Every $P_i$, $i = 1, \dots, k-1$, has at least one common vertex with $P_{i+1}$ which is an internal vertex.

This partition is used directly in the following theorem.

**Theorem 2.6** (Dolati, Hashemi, Khosravani [11]) *Given a digraph D. In every upward embedding of D on $T_h$, all arcs that belong to the same class R must be drawn on the same layer.*

## 3 Characterization

In this section we present a characterization of a digraph that has an upward embedding on the horizontal torus. Then, by using the characterization we show that the decision problem to decide whether a digraph has an upward embedding on the horizontal torus belongs to NP. Here, for the sake of the simplicity, by

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** (a) A horoidal digraph $G = (V, A, \{s\}, \{t\})$, (b) A non-stable $\{s\}\{t\}$-bipartition of $G$, (c) An inconsistent stable $\{s\}\{t\}$-bipartition of $G$, (d) A consistent stable $\{s\}\{t\}$-bipartition of $G$</figcaption></figure>

$D = (V, A, S, T)$ we mean a digraph $D$ with vertex set $V$, arc set $A$, source set $S$, and sink set $T$. For each $A_1 \subseteq A$, by $D(A_1)$ we mean the induced subdigraph on $A_1$. A bipartition $A_1$ and $A_2$ of $A$ is called an *ST-bipartition* and denoted by $[A_1, A_2]$ if the source set and sink set of both $D(A_1)$ and $D(A_2)$ are $S$ and $T$, respectively. Such a bipartition is called a *stable ST-bipartition* if all arcs of each equivalence class of $R$ belong to exactly one part. If $[A_1, A_2]$ is a stable ST-bipartition for which $D(A_1)$ and $D(A_2)$ are spherical then we call it a *consistent stable ST-bipartition*. See Fig. 1. As we will prove, a necessary condition for a digraph $D = (V, A, S, T)$ to be horoidal is that $D$ is a spanning subdigraph of a digraph $D' = (V, A', S', T')$ with a consistent stable $S'T'$-bipartition.

We need to introduce two more notions. For the sphere $S = \{(x, y, z) : x^2 + y^2 + z^2 = 1\}$ by the $c$-circle we mean one obtained from the intersection of $S$ with the plane $z = c$. For a finite set $S$, by a *permutation* $\pi_S$ of $S$ we mean a linear ordering of $S$.
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** (a) A super source of type *m*. (b) A super sink of type *n*. (c) An upward embedding of this super source (super sink) on sphere whose sinks (sources) lie on a $c_1$-circle ($c_2$-circle) for some $-1 < c_1 < c_2 < 1$.</figcaption></figure>

Let $D = (V, A, S, T)$ be a spherical digraph and $\pi_S$ and $\sigma_T$ be two permutations for $S$ and $T$, respectively. The digraph $D$ is called *ordered spherical* with respect to $\pi_S$ and $\sigma_T$ if it has an upward embedding in which the vertices in $S$ and $T$ lie on $c_1$-circle and $c_2$-circle for some $-1 < c_1 < c_2 < 1$, and are ordered (cyclically) by $\pi_S$ and $\sigma_T$, respectively. A digraph $D = (V, A, S, T)$ is called *bispherical* if there is a consistent stable $ST$-bipartition $[A_1, A_2]$ of $A$.

Let $\pi_S$ and $\sigma_T$ be two permutations for $S$ and $T$, respectively. A digraph $D = (V, A, S, T)$ is called *ordered bispherical* with respect to $\pi_S$ and $\sigma_T$, if there is a consistent stable $ST$-bipartition $[A_1, A_2]$ of $A$ such that $D(A_1)$ and $D(A_2)$ are ordered spherical with respect to $\pi_S$ and $\sigma_T$. A *super source* of type *m* is denoted by $S_m$ and is a single source digraph of order $2m+1$ whose vertex set is $V(S_m) = \{s, x_0, x_1, \dots, x_{m-1}, x'_0 x'_1, \dots, x'_{m-1}\}$ and its arc set is $A(S_m) = \{(s, x'_i) : i = 0, 1, \dots, m-1\} \cup \{(x'_i, x_i), (x'_i, x_{i-1}) : i = 0, 1, \dots, m-1\}$; here the indices are considered modulo $m$, see Figure 2. The vertices $\{x_0, x_1, \dots, x_{m-1}\}$ are the sinks of $S_m$. A super sink of type $n$ is denoted by $T_n$ and is a single sink digraph of order $2n+1$ whose vertex set is $V(T_n) = \{t, y_0, y_1, \dots, y_{n-1}, y'_0, y'_1, \dots, y'_{n-1}\}$ and its arc set is $A(T_n) = \{(y'_i, t) : i = 0, 1, \dots, n-1\} \cup \{(y_i, y'_i), (y_i, y'_{i-1}) : i = 0, 1, \dots, n-1\}$; here the indices are considered modulo $n$. See Fig. 2. The vertices $\{y_0, y_1, \dots, y_{n-1}\}$ are the sources of $T_n$. Let $D$ and $H$ be two digraphs such that $V(D) \cap V(H) = \emptyset$. Also suppose that $\{u_1, \dots, u_m\} \subseteq V(D)$ and $\{v_1, \dots, v_m\} \subseteq V(H)$, by $D \times \{(u_1 = v_1), \dots, (u_m = v_m)\} \times H$ we mean the digraph obtained from $D$ and $H$ by identifying the vertices $u_i$ and $v_i$, for $i = 1, \dots, m$. Suppose that $D = (V, A, S, T)$ is a digraph whose source set is $S = \{s_1, s_2, \dots, s_m\}$ and its sink set is $T = \{t_1, t_2, \dots, t_n\}$. Assume that $\pi_S$ and $\sigma_T$ are permutations for $S$ and $T$, respectively. Suppose that $S_m$ is a super source whose sink set is $\{x_0, x_1, \dots, x_{m-1}\}$ and $T_n$ is a super sink whose source set is $\{y_0, y_1, \dots, y_{n-1}\}$.
Let us denote the single source and single sink digraph obtained as

$$ (S_m \ltimes \{(x_0 = s_{\pi(0)}) \dots (x_{m-1} = s_{\pi(m-1)})\} \rtimes D) \ltimes \{(t_{\sigma(0)} = y_0) \dots (t_{\sigma(n-1)} = y_{n-1})\} \rtimes T_n $$
by $\pi_S D \sigma_T$.

**Lemma 3.7** Let $D = (V, A, S, T)$ be a digraph and $\pi_S$ and $\sigma_T$ be permutations for $S$ and $T$, respectively. The digraph is ordered spherical with respect to the permutations $\pi_S$ and $\sigma_T$ if and only if $\pi_S D \sigma_T$ is spherical.

*proof.* If $\pi_S D \sigma_T$ is spherical, then it is not hard to observe that, we can redraw the graph, if necessary, to obtain an upward embedding of $\pi_S D \sigma_T$ in which the vertices of $S$ lie on a $c_1$-circle and also the vertices of $T$ lie on a $c_2$-circle preserving their permutations. The proof of the other side of the lemma is obvious. ■

Consider the round sphere $S = \{(x, y, z)|x^2 + y^2 + z^2 = 1\}$, by $S_z^\epsilon$ we mean the portion of the sphere between the two level curves obtained by cutting the sphere with parallel planes $Z = z$ and $Z = z + \epsilon$, for all $-1 < z < 1$ and all $0 < \epsilon < 1 - z$. Note that, every upward embedding of a digraph $D$ on sphere $S$ can be redrawn to be an upward embedding on $S_z^\epsilon$, for all $-1 < z < 1$ and all $0 < \epsilon < 1 - z$. According to this observation, we can show that for upward embedding of digraphs, each layer of $T_h$ is equivalent to the round sphere. It is summarized in the following proposition.

**Proposition 3.8** The digraph $D$ has an upward embedding on a layer of $T_h$ if and only if it has an upward embedding on the round sphere $S = \{(x, y, z)|x^2 + y^2 + z^2 = 1\}$.

By the following theorem we characterize the horoidal digraphs. We assume w.l.o.g. that the digraphs have no isolated vertex.

**Theorem 3.9** The digraph $D = (V, A, S, T)$ has an upward embedding on the horizontal torus if and only if there are subsets $S' \subseteq S$ and $T' \subseteq T$ and there are permutations $\pi_{S'}$ and $\sigma_{T'}$ such that by adding new arcs, if necessary, the digraph can be extended to a digraph $D' = (V, A', S', T')$ which is ordered spherical or ordered bispherical with respect to $\pi_{S'}$ and $\sigma_{T'}$.

*proof.* Suppose that $D = (V, A, S, T)$ has an upward embedding on $T_h$. There are two cases that can be happen for $D$.

Case 1. $D$ has an upward embedding on a layer of $T_h$. In this case, according to Proposition 3.8 it has an upward embedding on sphere. By Theorem 1.3 we conclude that $D$ is a spanning subdigraph of a single source and single sink digraph $D' = (V, A', S', T')$. That means the assertion for this case follows. Because $D'$ is an ordered spherical with respect to the unique permutation of $S'$ and $T'$.

Case 2. $D$ has no upward embedding on a layer of $T_h$. In this case we consider an upward embedding of $D$ on $T_h$. Suppose that, the subset of sources (sinks) that must be placed on $c_{min}(c_{max})$ is denoted by $S'(T')$. Now, we add a set of new arcs $F$ to this embedding in such way that all of them point up, they do
<figure><img src="image_4.png" /><figcaption>Fig. 3. A digraph $D = (V, A, \{s'\}, \{t'\})$ that is not horoidal</figcaption></figure>

not generate crossing and for each source node in $S \setminus S'$ (sink node in $T \setminus T'$) there will be an arc in $F$ incoming to (emanating from) it. By adding this set of arcs we have an upward embedding of a superdigraph $D' = (V, A', S', T')$ of $D = (V, A, S, T)$ in which $A' = A \cup F$. Suppose that we denote by $\pi_S'$ and $\sigma_T'$ the permutations of $S'$ and $T'$ according to their order of their placement on $c_{min}$ and $c_{max}$, respectively. Let $A_{in}$ and $A_{out}$ be the set of arcs drawn on the inner layer and outer layer of $T_h$, respectively. The digraphs $D'(A_{in})$ and $D'(A_{out})$ are order spherical with respect to $\pi_S'$ and $\sigma_T'$. In other words, $D' = (V, A', S', T')$ is a superdigraph of $D = (V, A, S, T)$ and is orderd bispherical with respect to $\pi_S'$ and $\sigma_T'$.

Conversely, suppose that, there is a superdigraph $D' = (V, A', S', T')$ of $D$ that is an orderd spherical with respect to some permutations of $S'$ and $T'$, for some $S' \subset S$ and $T' \subset T$. In this case, $D'$ is a horoidal digraph and therefore its subdigraph $D$ is also horoidal.

Now, suppose that there are some subsets $S' \subset S$ and $T' \subset T$ and some permutations $\pi_S'$ and $\sigma_T'$ for them such that a superdigraph $D' = (V, A', S', T')$ of $D$ is ordered bispherical with respect to $\pi_S'$ and $\sigma_T'$. Let $[A_1, A_2]$ be its corresponding consistent stable $S'T'$-bipartition. In this case, the digraphs $D'(A_1)$ and $D'(A_2)$ are ordered spherical with respect to $\pi_S'$ and $\sigma_T'$. Therefore, the digraph $D'(A_1)$ and $D'(A_2)$ can be embedded upwardly on inner layer and outer layer of $T_h$, respectively such that these upward embeddings imposes an upward embedding for $D'$ on $T_h$. In other words, $D'$ and therefore $D$ has an upward embedding on the horizontal torus. ■

We characterize the horoidal digraphs by the above theorem. Note that, one can not apply it for characterization the digraphs that admit upward embedding on
vertical torus. As an example, all arcs in $\mathcal{A}$ in every stable $\{s'\}\{t'\}$-bipartition of every super graph $D' = (\mathcal{V}, \mathcal{A}', \{s'\}, \{t'\})$ of digraph $\mathcal{D} = (\mathcal{V}, \mathcal{A}, \{s'\}, \{t'\})$ depicted in Fig. 3 belong to one part. That means it is inconsistent. Because $k_{3,3}$ is a subgraph of the underlying graph of indeced subdigraph on the aforementioned part. Therefore, this digraph is not horoidal. However, one of its upward embeddings on vertical torus is depicted in [11].

Now, by using the characterization stated in Theorem 3.9 we show that
Problem 3 belongs to NP. It is summarized in the following theorem.

**Theorem 3.10** The upward embedding testing on $T_h$ belongs to NP.

*proof.* The candidate solution consists of a superdigraph $D' = (\mathcal{V}, \mathcal{A}', \mathcal{S}', \mathcal{T}')$ of the instance $\mathcal{D}$ whose sources and sinks are subsets of the sources and sinks of $\mathcal{D}$, two cyclic permutations $\pi_S'$ and $\sigma_T'$ for $\mathcal{S}'$ and $\mathcal{T}'$ and a consistent stable $\mathcal{S}'\mathcal{T}'$-bipartition $[A_1, A_2]$, if necessary. For checking the correctness of this solution in polynomial time, one can check the conditions of Theorem 3.9. To this end, the Step 1 of the following two steps can be considered and if it is not sufficient (i.e., if the answer of Step 1 is not true) then another step must be considered, too.

*Step 1.* Check if the digraph $D'$ is an ordered spherical with respect to $\pi_S'$ and $\sigma_T'$.

*Step 2.* Check if the digraphs $D'(A_1)$ and $D'(A_2)$ are ordered spherical with respect to $\pi_S'$ and $\sigma_T'$.

For checking Step 1, it suffices to check if the single source and single sink digraph $\pi_S' D' \sigma_T'$ is spherical. According to Theorem 1.3 it can be done by checking if its underlying graph is planar. Therefore this checking step can be done in polynomial time. If it is revealed that its underlying graph is not planar then by using $[A_1, A_2]$ we have to consider Step 2. For checking Step 2 it is sufficient to check if the single source and single sink digraphs $D'(A_1)$ and $D'(A_2)$ are ordered spherical with respect to $\pi_S'$ and $\sigma_T'$. Similarly, this step can be checked in polynomial time. Therefore the candidate solution can be checked in polynomial time. That means the assertion follows.

■

# 4 Source-in-sink-out graph of adigraph

In this section we want to show that the upward embedding testing problem on $T_h$ is an NP-hard problem. We do this by a polynomial time reduction from the upward sphericity testing decision problem. Let $x$ and $y$ be two vertices of a digraph $\mathcal{D}$. By $y \prec x$ we mean the vertex $x$ is reachable from the vertex $y$. That means there is a directed path from $y$ to $x$ in $\mathcal{D}$, especially $y$ is reachable from itself by the trivial path. By $N^+(y)$ we mean all the reachable vertices from $y$ and by $N^-(y)$ we mean all the vertices for which $y$ is a reachable vertex. A subgraph $D_x^O = (V(D_x^O), A(D_x^O))$ is an *out-subgraph* rooted at vertex $x$ if $V(D_x^O) = N^+(x)$ and $A(D_x^O)$ consists of all the arcs of all the directed paths in $\mathcal{D}$ from $x$ to every other vertex in $V(D_x^O)$. A subgraph $D_x^I = (V(D_x^I), A(D_x^I))$ is
an in-subgraph rooted at vertex $x$ if $V(D) = N^{-}(x)$ and $A(D_{x}^{I})$ consists of all the arcs of all the directed paths in $D$ from every other vertex in $V(D_{x}^{O})$ to $x$. In Fig. 4 an out-subgraph rooted at a source vertex is depicted. Now, we are ready

<figure><img src="image_5.png" /><figcaption>Fig. 4. A digraph $D$ and the arcs of $D_{s_1}^O$.</figcaption></figure>

to introduce some useful properties of these defined subgraphs.

**Lemma 4.11** Let $x$ be an internal vertex of a digraph $D$, then all the arcs in $A(D_x^O) \cup A(D_x^I)$ belong to the same equivalence class with respect to the relation $\mathbf{R}$.

**Proof.** The internal vertex $x$ has both incoming and outgoing arcs. Let $a$ and $a'$ be an incoming arc of $x$ and an outgoing arc of $x$, respectively. For each arc in $A(D_x^O)$ there is a directed path containing that arc and $a$, therefore they belong to the same equivalence class. Similarly, for each arc in $A(D_x^I)$ there is a directed path containing that arc and $a'$, therefore they belong to the same equivalence class. On the other hand, there is a directed path containing $a$ and $a'$, that means they belong to the same equivalence class too. According to the transitive property of $\mathbf{R}$ the proof is completed. $\blacksquare$

The relation between the arcs of the out-subgraph rooted at a source vertex and the relation between the arcs of the in-subgraph rooted at a sink vertex are shown in the following lemma.

**Lemma 4.12** Let $s$ and $t$ be a source vertex and a sink vertex of a digraph $D$, respectively.

(i) If $od(s) = 1$ then all the arcs of $D_s^O$ belong to the same equivalence class with respect to the relation $\mathbf{R}$.

(ii) If $id(t) = 1$ then all the arcs of $D_t^I$ belong to the same equivalence class with respect to the relation $\mathbf{R}$.
**Proof.** Suppose that $od(s) = 1$ and let $a$ be the outgoing arc of $s$. Obviously, for each arc of $D_s^O$ there is a directed path containing that arc and $a$, therefore they belong to the same equivalence class. That means all the arcs of $D_s^O$ belong to the same equivalence class with respect to the relation $\mathbf{R}$. Similarly, the second part of the lemma can be proved. ■

Now, we define the *source-in-sink-out graph* of a digraph $D = (V, A)$ that is denoted by $SISO(D)$. Suppose that $D = (V, A)$ is a digraph with the set of source vertices $S$ and the set of sink vertices $T$. Let $S = \{s \in S \mid od(s) > 1\}$ and let $T = \{t \in T \mid id(t) > 1\}$. In other words, $S$ is the set of sources for which the number of their outgoing arcs is more than one and $T$ is the set of sinks for which the number of their incoming arcs is more than one. Construction of the digraph $SISO(D)$ from the digraph $D$ is done as follows. For each source vertex $s \in S$, we add a new vertex $s'$ and a new arc from the new vertex $s'$ to the vertex $s$. Also, for each sink vertex $t \in T$, we add a new vertex $t'$ and a new arc from the vertex $t$ to the new vertex $t'$ (see Figure 5). Obviously, $s'$ is a source vertex, $t'$ is a sink vertex, and $s$ and $t$ are two internal vertices of $SISO(D)$. With respect to the construction of $SISO(D)$, we can immediately conclude the

<figure><img src="image_6.png" /><figcaption>Fig. 5. The source-in-sink-out graph of the depicted graph in Fig 4</figcaption></figure>

following lemma.

**Lemma 4.13** Let $D$ be a digraph.

(i) If $s$ is a source vertex of $SISO(D)$ then $od(s) = 1$.

(ii) If $t$ is a sink vertex of $SISO(D)$ then $id(t) = 1$.

By Definition 2.5 two arcs of a digraph belong to the same equivalence class if they belong to a directed path. In the following lemma we show that two arcs of
a source-in-sink-out graph belong to the same class if they belong to the same
undirected path (not necessarily directed).

**Lemma 4.14** *Suppose that D is a digraph. If P is an undirected path in SISO(D), then all the arcs of P belong to the same equivalence class with respect to the relation R.*

**Proof.** It is sufficient to show that each pair of consecutive arcs in $P$ belong to the same equivalence class. To this end let $a$ and $a'$ be an arbitrary pair of consecutive arcs of $P$, and let $v$ be their common vertex. Since the number of the arcs incident with $v$ is at least two, by Lemma 4.13, the vertex $v$ is neither a source vertex of $SISO(D)$ nor a sink vertex of $SISO(D)$. That means $v$ is an internal vertex of $SISO(D)$. Therefore by Lemma 4.11, the arcs $a$ and $a'$ belong to the same equivalence class. $\blacksquare$

The following theorem states a key property of the source-in-sink-out graph of
a digraph.

**Proposition 4.15** *Let $D$ be a connected digraph, all the arcs of $SISO(D)$ be-long to the same equivalence class with respect to $\mathbf{R}$.*

**Proof.** Let $a = (x, y)$ and $a' = (x', y')$ be an arbitrary pair of arcs of $D$. Because of the connectivity of $D$, there is an undirected path $P'$ between $x$ to $y'$. If $P'$ does not contain $a$, we add it to $P'$. In this case the starting point of the obtained undirected path is the vertex $y$. Similarly, we can add the arc $a'$ to the undirected path, if it does not contain this arc. In other words, there is an undirected path $P$ in $D$ that contains $a$ and $a'$. Thus, by Lemma 4.14, $a$ and $a'$ belong to the same equivalence class. $\blacksquare$

In the following theorem we observe that either both digraphs $D$ and $SISO(D)$
or none of them have upward embeddings on sphere.

**Proposition 4.16** *The digraph $D$ has an upward embedding on sphere if and only if $SISO(D)$ has an upward embedding on sphere.*

**Proof.** Suppose that we have an upward embedding of $D$ on the round sphere $S = \{(x, y, z) | x^2 + y^2 + z^2 = 1\}$. Let $S$ be the set of sources for which the number of their outgoing arcs is more than one and let $\mathcal{T}$ be the set of sinks of $D$ for which the number of their incoming arcs is more than one. Without loss of generality, we can assume that none of the sources (sinks) of $S$ ($\mathcal{T}$) is located at south (north) pole. Otherwise, we may modify the upward embedding to provide an upward embedding on the sphere with this property. Let $s \in S$ be an arbitrary source in $S$ with $z$ its height (its $z$-coordinate) and consider $S_{z-\epsilon}^c$, where $\epsilon$ is small enough so that this portion contains no vertices of $D$ in its interior. This portion may be partitioned into connected regions bounded by the monotonic curves corresponding to the arcs of $D$. We consider a point $s'$ as an arbitrary point on the circle obtained by cutting the sphere with plane $Z = z - \epsilon$ so that the point $s$ and $s'$ are on the boundary of a region. Now, we draw the arc $(s', s)$ in the mentioned region by a monotonic curve. Similarly, if we draw an arc $(t, t')$ for each sink $t \in \mathcal{T}$ by a monotonic curve without any crossing with other arcs.
Then we have an upward embedding for $SISO(D)$ on the round sphere. Conversely, if we have an upward embedding of $SISO(D)$ on the round sphere. By deleting all added arcs $(s', s)$ and $(t, t')$ in construction of $SISO(D)$ from $D$, we have an upward embedding of $D$ on sphere. ■

**Proposition 4.17** Let $D$ be a digraph, $SISO(D)$ has an upward embedding on sphere if and only if it has an upward embedding on $T_h$.

**Proof.** Suppose that $SISO(D)$ has an upward embedding on sphere. Since, for upward embedding, sphere and each layer of $T_h$ are equivalent we can conclude that $SISO(D)$ has an upward embedding on a layer of $T_h$ and therefore on $T_h$. Conversely, suppose that $SISO(D)$ has an upward embedding on $T_h$. By Proposition 4.15, all the arcs of each connected component of $SISO(D)$ belong to the same equivalence class with respect to relation $R$. Therefore, by Theorem 2.6 in any upward embedding of $SISO(D)$ on $T_h$ all the arcs of each connected component of $SISO(D)$ must be drawn on a layer of $T_h$. Suppose that $SISO(D)$ has $k$ connected components and let $H_1, H_2, \dots, H_k$ be its connected components. Assume that $-1 < z < 1$ is a real number. We set $\epsilon = \frac{1-z}{k+1}$, and embed the component $H_j$ on the portion $S_{z+(j-1)\epsilon}^\epsilon$ upwardly, for $j = 1, \dots, k$. In other words, we can have an upward embedding of $SISO(D)$ on the round sphere. ■ Now, by Proposition 4.16 and Proposition 4.17 we have the following theorem:

**Proposition 4.18** The digraph $D$ has an upward embedding on sphere if and only if $SISO(D)$ has an upward embedding on $T_h$.

Obviously, the construction of $SISO(D)$ from $D$ can be done in $O(n)$ time, where $n$ is the number of vertices of $D$. By this fact and Proposition 4.18 the NP-hardness of upward embedding testing on $T_h$ is proved, this is summarized in the following theorem.

**Theorem 4.19** The upward embedding testing on $T_h$ is an NP-hard problem.

By Theorem 3.10 and Theorem 4.19 we have one of the main results of the paper as follows.

**Theorem 4.20** The upward embedding testing on $T_h$ is an NP-Complete problem.

# 5 Conclusion and some open problems

In this paper, we have presented a characterization for a digraph to have an upward embedding on $T_h$. By that characterization we have shown that the decision problem to decide whether a digraph has an upward embedding on the horizontal torus belongs NP. We have constructed a digraph from a given digraph in such a way that it is horoidal if and only if it is spherical. Finally, we have presented a polynomial time reduction from the sphericity testing decision
problem to the upward embedding testing on $T_h$. That means we have shown
that the upward embedding testing decision problem on $T_h$ is NP-Complete.

The following are some open problems:

Dolati et. al in [11] presented a polynomial time algorithm to decide whether a
single source and single sink digraph has an upward embedding on $T_h$.

**Problem 1:** Is it possible to find polynomial time algorithms for upward embedding testing of some other classes of digraphs on $T_h$?

**Problem 2:** Characterize those digraphs which they are shperical if and only if they are horoidal.

**Acknowledgements** I am very thankful to Dr. Masoud Khosravani for his helpful discussions. I am also very grateful to anonymous referees for their usefull suggestions and comments.

**References**

1. Auer C., Bachmaier C., Brandenburg F.J., Gleiner A.: Classification of planar upward embedding, in: M. van Kreveld, B. Speckmann (Eds.), Proc. 19th International Symposium on Graph Drawing, GD 2011, in: LNCS, vol.7034, Springer Verlag, Heidelberg, Germany, pp.415-426 (2011).

2. Auer C., Bachmaier C., Brandenburg F.J., Gleiner A., Hanauer K.: The duals of upward planar graphs on cylinders, in: M.C. Golumbic, M. Stern, A. Levy, G. Morgenstern (Eds.), Proc. 38th Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012, in: LNCS, vol.7551, Springer Verlag, 103-113 (2012).

3. Auer C., Bachmaier C., Brandenburg F.J., Hanauer K.: Rolling upward planarity testing of strongly connected graphs, in: A. Brandstättd, K. Jansen, R. Reischuk (Eds.), Proc. 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013, in: LNCS, vol.8165, Springer Verlag, Heidelberg, Germany, 38-49 (2013).

4. Auer C., Bachmaier C., Brandenburg F. J., Gleiner A., Hanauer K.: Upward planar graphs and their duals. Theor. Comput. Sci. **571**, 36-49 (2015).

5. Bertolazzi P., Di Battista G., Liotta G., and Mannino C.: Upward drawing of triconnected digraphs. Algorithmica. **12**(6), 476-497 (1994).

6. Bertolazzi P., Di Battista G., Mannino C., and Tamassia R.: Optimal upward planarity testing of single source digraphs. SIAM J. Comput. **27**(1), 132-169 (1998).

7. Di Battista G., Tamassia R.: Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science. **61**, 175-198 (1988).

8. Dolati A.: Digraph embedding on $T_h$, in: Proc. Seventh Cologne Twente Workshop on Graphs and Combinatorial Optimization, CTW 2008, University of Milan, 11-14 (2008).

9. Dolati A.: Linear Sphericity Testing of 3-Connected Single Source Digraphs. Bulletin of the Iranian Mathematical Society. **37**(3), 291-304 (2011).

10. Dolati A., Hashemi S.M.: On the sphericity testing of single source digraphs. Discrete Mathematics. **308** (11), 2175-2181 (2008).
11. Dolati A., Hashemi S.M., and Khosravani M.: On the Upward Embedding on the Torus, Rocky Mountain Journal of Mathematics. **38 (1)**, 107-121 (2008).

12. Filotti I.S., Miller G.L., and Reif J.: On determining the genus of a graph in $O(v^O(g))$ steps, in Proceeding of the 11th Annual Symposium on Theory of Computing, ACM Press, New York. 27-37 (1979).

13. Garg A., Tamassia R.: On the Computational Complexity of Upward and Rectilinear Planarity Testing (Extended Abstract), *R. Tamassia and I.G. Tollis(eds.)*, *Graph Drawing '94, Lecture Notes in Computer Science*, Vol. 894, Springer, Berlin, pp. 286-297 (1994).

14. Garg A., Tamassia R.: Upward planarity testing. Order. **12 (2)**, 109-133 (1995).

15. Hashemi S. M.; Digraph embedding. Discrete Mathematics. **233**, 321-328 (2001).

16. Hashemi S. M., Rival I.: Upward drawing to fit surfaces, in: *Orders, Algorithms, and Applications*, (ORDAL'94) (eds. Bouchitté, V., and M. Morvan, M.), *Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, New York*, **831**, 53-58 (1994).

17. Hashemi S. M., Rival I.: and Kisielewicz A.: The Complexity of Upward Drawings on Spheres. Order. **14**, 327-363 (1998).

18. Hutton M. and Lubiw A.: Upward Planar Drawing of Single-Source Acyclic Digraph. SIAM J. Comput. **25 (2)**, 291-311 (1996).

19. Kelly D.: Fudamental of planar ordered sets. Discrete Mathematics. **63**, 197-216 (1987).

20. Papakostas A.: Upward planarity testing of outerplanar dags, in: *R. Tamassia and I. G. Tollis(eds.)*, *Graph Drawing '94, Lecture Notes in Computer Science* 894, Springer, 298-306 (1994).

21. Thomassen, C.: Planar Acyclic Oriented Graphs. Order. **5** 349-361. (1989)