Ortho-polygon Visibility Representations of Embedded Graphs

Abstract

An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding-preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if G has at most one crossing per edge (i.e., G is a 1-plane graph), an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute an OPVR of G whose vertex complexity is bounded by a constant in O(n) time. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be $\varOmega (n)$. In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O(n) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs.

Appendices

Appendix A: Orthogonal Representations and Network Flow Model

In this section, we recall basic definitions and main results related to the problem of computing orthogonal representations exploiting the network flow model by Tamassia. We refer the reader to [13, 21] for further details.

Let G be a plane graph (possibly with multiple edges and self-loops) whose maximum vertex degree is four. Let $e=(u,v)$ be an edge of G. The two possible orientations (u, v) and (v, u) of e are called darts. A dart is said to be counterclockwise with respect to face f if f is on the left hand side when walking along the dart according to its orientation. Denote by D(u) the set of darts exiting from u and by D(f) the set of counterclockwise darts with respect to f.

An orthogonal representation of G is an assignment to each dart (u, v) of two values $\alpha (u,v) \in \{1,2,3,4\}$ and $\beta (u,v) \in \mathbb {N}$ that satisfies the following conditions.

C1. :

$1 \le \alpha (u,v) \le 4$;

C2. :

$\beta (u,v) \ge 0$;

C3. :

$\sum _{(u,v) \in D(u)}\alpha (u,v)=4$;

C4. :

For each internal face f: $\sum _{(u,v) \in D(f)}(\alpha (u,v)+\beta (v,u)-\beta (u,v))=2\deg (f)-4$;

C5. :

For the outer face $f_{ext}$: $\sum _{(u,v) \in D(f_{ext})}(\alpha (u,v)+\beta (v,u)-\beta (u,v))=2\deg (f)+4$.

The value $\alpha (u,v)\cdot \frac{\pi }{2}$ is the angle that dart (u, v) forms with the dart following it in the circular counterclockwise order around u, while the value $\beta (u,v)$ is the number of bends of $\frac{\pi }{2}$ along the dart (u, v). Condition C1 expresses the fact that the sum of angles around each vertex is $2\pi$, while C2 (respectively C3) expresses the fact that the sum of the angles at the vertices and bends of an internal face (respectively outer) is equal to $\pi (p-2)$ (respectively $\pi (p+2)$), where p is the number of such angles.

An orthogonal representation of G with the minimum number of bends can be computed by means of a flow network N. In the flow network N, each unit of flow corresponds to a $\frac{\pi }{2}$ angle, each vertex supplies 4 units of flow, and each face consumes an amount of flow proportional to its degree. Bends along edges correspond to unit of flows transferred across adjacent faces, and each bend has a unit cost in the network. The flow network N is constructed as follows. The nodes of network N are the vertices and faces of G. Each vertex-node v supplies $\sigma (v)=4$ units of flow, and each face-node f consumes $\tau (f)$ units of flow, where

$$\begin{aligned} \tau (f) = \left\{ \begin{array}{l l} 2 \deg (f) - 4 &{} \text{ if } \text{ f } \text{ is } \text{ an } \text{ internal } \text{ face }\\ 2 \deg (f) + 4 &{} \text{ if } \text{ f } \text{ is } \text{ the } \text{ outer } \text{ face. } \end{array} \right. \end{aligned}$$

By Euler’s formula, $\sum _v \sigma (v) = \sum _f \tau (f)$, i.e., the total supply is equal to the total consumption.

For each dart (u, v) of G, with faces f and g on its left and right, respectively, N has two arcs:

• an arc (u, f) with lower bound $\lambda (v,f)=1$, capacity $\mu (v,f)=4$, and cost $\chi (v,f)=0$;

• an arc (f, g) with lower bound $\lambda (v,f)=0$, capacity $\mu (v,f)=+\infty$, and cost $\chi (v,f)=1$;

The conservation of flow at the vertices expresses the fact that the sum of the angles around a vertex is equal to $2 \pi$. The conservation of flow at the faces expresses the fact that the sum of the angles at the vertices and bends of an internal face is equal to $\pi (p-2)$, where p is the number of such angles. For the outer face, the above sum is equal to $\pi (p+2)$.

It can be shown that every feasible flow $\phi$ in network N corresponds to an admissible orthogonal representation for graph G, whose number of bends is equal to the cost of flow $\phi$. Namely, let $\varPhi$ be a flow of N with cost b. Then, for each dart (u, v) whose associated arcs of N are (u, f) and (f, g), we set $\alpha (u,v)=\varPhi (u,f)$ and $\beta (u,v) = \varPhi (f,g)$. On the other hand, by just setting $\varPhi (u,f)=\alpha (u,v)$ and $\varPhi (f,g)=\beta (u,v)$, an orthogonal representation H with at most b bends is transformed into a feasible flow $\varPhi$ of N with cost b. Hence, the following theorem summarizes the above discussion.

Theorem 9

(see e.g. [13]) Let G be a plane graph with n vertices and maximum vertex degree four. An orthogonal representation H of G with the minimum number of bends can be computed in O(T(n)) time, where T(n) is the time for computing a min-cost flow of the flow network N associated with G.

Appendix B: The SPQR-Tree Decomposition

The following definitions and observations are useful for the proof of Theorem 8.

Let G be a 2-connected graph. A separation pair is a pair of vertices whose removal disconnects G. A split pair is either a separation pair or a pair of adjacent vertices. A split component of a split pair $\{u,v\}$ is either an edge (u, v) or a maximal subgraph $G_{uv} \subset G$ such that $\{u,v\}$ is not a split pair of $G_{uv}$. Vertices $\{u,v\}$ are the poles of $G_{uv}$. The SPQR-tree T of G with respect to an edge e is a rooted tree that describes a recursive decomposition of G induced by its split pairs [14]. In what follows, we call nodes the vertices of T, to distinguish them from the vertices of G. The nodes of T are of four types S,P,Q, or R. Each node $\mu$ of T has an associated 2-connected multigraph called the skeleton of $\mu$ and denoted by $sk(\mu )$. At each step, given the current split component $G^*$, its split pair $\{s,t\}$, and a node $\nu$ in T, the node $\mu$ of the tree corresponding to $G^*$ is introduced and attached to its parent vertex $\nu$, while the decomposition possibly recurs on some split component of $G^*$. At the beginning of the decomposition the parent of $\mu$ is a Q-node corresponding to $e=(u,v), G^* = G \setminus e$, and $\{s,t\} = \{u,v\}$.

Fig. 21

a A graph G; b the SPQR-tree T of G. For each node that is not a Q-tree the skeleton is depicted in the gray balloons; for Q-nodes the corresponding edge is shown

Base case: $G^*$ consists of a single edge between s and t. Then, $\mu$ is a Q-node whose skeleton is $G^*$ itself plus the reference edge between s and t.

Parallel case: The split pair $\{s,t\}$ has $G_1,\ldots ,G_k$ ($k \ge 2$) split components. Then, $\mu$ is a P-node whose skeleton is a set of $k+1$ parallel edges between s and t, one for each split component $G_i$ plus the reference edge between s and t. The decomposition recurs on $G_1,\ldots ,G_k$ with $\mu$ as parent node.

Series case: $G^*$ is not 2-connected and it has at least one cut vertex (a vertex whose removal disconnects $G^*$). Then, $\mu$ is an S-node whose skeleton is defined as follows. Let $v_1,\ldots ,v_{k-1}$, where $k \ge 2$, be the cut vertices of $G^*$. The skeleton of $\mu$ is a path $e_1,\ldots ,e_k$, where $e_i= (v_{i-1},v_i), v_0=s$ and $v_k=t$, plus the reference edge between s and t which makes the path a cycle. The decomposition recurs on the split components corresponding to each $e_1,\ldots ,e_k$ with $\mu$ as parent node.

Rigid case: None of the other cases is applicable. A split pair $\{s',t'\}$ is maximal with respect to $\{s,t\}$, if for every other split pair $\{s^*,t^*\}$, there is a split component that includes the vertices $s',t',s,t$. Let $\{s_1,t_1\},\ldots ,\{s_k,t_k\}$ be the maximal split pairs of $G^*$ with respect to $\{s,t\}$ ($k \ge 1$), and, for $i=1,\ldots ,k$, let $G_i$ be the union of all the split components of $\{s_i,t_i\}$. Then $\mu$ is an R-node whose skeleton is obtained from $G^*$ by replacing each component $G_i$ with an edge between $s_i$ and $t_i$, plus the reference edge (s, t). The decomposition recurs on each $G_i$ with $\mu$ as parent node.

Figure 21 shows a graph and its SPQR-tree. For each node that is not a Q-tree the skeleton is depicted; for Q-nodes the corresponding edge is shown. The SPQR-tree T of a graph G with n vertices and m edges has m Q-nodes and O(n) S-, P-, and R-nodes. Also, the total number of vertices of the skeletons stored at the nodes of T is O(n).

If G is an embedded graph, then each pertinent graph $G_\mu$ of a node $\mu$ of T is also an embedded graph. Furthermore, the skeleton $sk(\mu )$ of $\mu$ inherits an embedding from $G_\mu$. For our purposes, we observe that if G is a 1-plane graph, then the skeleton of an R-node is also a 1-plane graph. Moreover, we remark that the skeleton of an R-node is 3-connected by definition.

The SPQR-tree can also be exploited to modify the embedding of G. A split component can be flipped around its poles, hence reversing the order of the edges of the split component around its poles. A swap operation consists of exchanging the position of two split components of the same split pair. If G is 1-plane, both these operations modify the embedding of G without introducing additional crossings, and thus preserve 1-planarity.