Drawing Graphs:Visibility Drawing

Visibility Drawing

In general, a visibility representation of a graph has a geometric shape for each vertex, and a “line of sight” for each edge. Different visibility representations involve different kinds of geometric shapes and different restrictions on the “line of sight”. A three dimensional visibility representation of the complete graph on five vertices is in Figure 46.12. Here the geometric objects are rectangular prisms, and each “line of sight” is parallel to a coordinate axis.

Visibility representations have been extensively investigated in both two and three dimensions.

For two dimensional graph drawing, the simplest and most common visibility representation uses horizontal line segments (called “bars”) for vertices and vertical line segments for “lines of sight”. More precisely, a bar visibility representation of a graph G = (V, E) consists of a horizontal line segment ωu for each vertex u ∈ V , and a vertical line segment λe for each edge e ∈ E, such that the following properties hold:

P1: If u and ul are distinct vertices of G, then ωu has empty intersection with ωul . P2: If e and el are distinct edges of G, then λe has empty intersection with λel .

P3: If e is not incident with u then λe has empty intersection with ωu.

P4: If e is incident with u then the intersection of λe and ωu consists of an endpoint of λe on ωu.

It is clear that if G admits a bar visibility representation, then G is planar. Tamassia and Tollis [34] and Rosenstiehl and Tarjan [32] proved the converse: every planar graph has a bar visibility representation. Further, they showed that the resulting drawing has quadratic area, that is, the resolution is good. The algorithms from [34] and [32] construct such a representation in linear time.

In the Section 46.5.1 below we describe some concepts used to present the algorithm. Section 46.5.2 describes the basic algorithm for constructing bar visibility representations, and Sections 46.5.3 and 46.5.4 show how to apply these representations to obtain layered drawings and orthogonal drawings respectively.

The algorithm in Section 46.5.2 and some of the preceding results are stated in terms of biconnected planar graphs. Note that this restriction can be avoided by augmenting graphs of lower connectivity with dummy edges.

Planar st-Graphs

Bar visibility representation algorithms use the theory of planar st-graphs. This is a powerful theory which is useful in a variety of graph drawing applications. In this section we describe enough of this theory to allow presentation of a bar visibility algorithm; for proofs of the results here, and more details about planar st-graphs, see [8].

A directed plane graph is a planar st-graph if it has one source s and one sink t, and both s and t are on the outside face. We say that a vertex u on a face f of a planar st-graph is a source for f (respectively sink for f ) if the edges incident with u on f are out-edges (respectively in-edges).

LEMMA 46.2 Every face f of a planar st-graph has one source sf for f and one sink tf for f .

The following Lemma (see [8] for a proof) is important for the bar visibility algorithm.

LEMMA 46.3

Suppose that f and f l are faces in a planar st-graph G. Then precisely one of the following statements is true.

(a) There is a directed path in G from the sink of f to the source of f l.

(b) There is a directed path in G from the sink of f l to the source of f .

(c) There is a directed path in G∗ from vf to vf l .

(d) There is a directed path in G∗ from vf l to vf .

The next Lemma is, in a sense, dual to Lemma 46.2.

LEMMA 46.4 Suppose that u is a vertex in a planar st-graph. The outgoing edges from u are consecutive in the circular ordering of N (u), and the incoming edges are consecutive in the circular ordering of N (u).

Lemma 46.4 leads to a definition of the lef t and right of a vertex. Suppose that (e1, e2,... , ek ) is the circular list of edges around a non-source non-sink vertex u, in clock- wise order. From Lemma 46.4, for some i, edge ei comes into u and edge ei+1 goes out from u. we say that ei is the leftmost in-edge of u and ei+1 is the leftmost out-edge of u. If f is the face shared by ei and ei+1 then we define lef t(u) = f . Similarly, there is a j such that edge ej goes out from u and edge ej+1 comes into u; we say that ej is the rightmost out-edge of u and ej+1 is the rightmost in-edge of u. If f l is shared by ej and ej+1 then we define right(ej ) = f l. If u is either the source or the sink, then lef t(u) = £ext and right(u) = rext.

In Figure 46.14, for example, lef t(a) = lef t(d) = 1, lef t(b) = 2, lef t(c) = 3, right(b) = 4, and right(a) = right(c) = right(d) = 5.

Finally, we need the following Lemma, which is a kind of dual to Lemma 46.3.

LEMMA 46.5

Suppose that u and ul are vertices in G. Then precisely one of the following statements is true.

(a) There is a directed path in G from u to ul.

(b) There is a directed path in G from ul to u.

(c) There is a directed path in G∗ from right(u) to lef t(ul).

(d) There is a directed path in G∗ from right(ul) to lef t(u).

The Bar Visibility Algorithm

The bar visibility algorithm takes a biconnected plane graph as input, and converts it to a planar st-graph. Then it computes the directed dual, and a “topological number” (defined below) for each vertex in both the original graph and the dual. Using these numbers, it assigns a y coordinate for each vertex and an x coordinate for each edge. The bar representing the vertex extends far enough to touch each incident edge, and the vertical line representing the edge extends far enough to touch each the bars representing its endpoints. If G = (V, E) is an acyclic directed graph with n vertices, a topological numbering Z of G assigns an integer Z(u) ∈ {0, 1,... ,n − 1} to every vertex u ∈ V such that Z(u) < Z(v) for all directed edges (u, v) ∈ E. Note that we do not require that the function Z be one-one, that is, it is possible that two vertices are assigned the same number.

The algorithm is described below.

Algorithm Bar Visibility

Input: a biconnected plane graph G = (V, E)

Output: a bar visibility representation of G

1. Choose two vertices s and t of G on the same face.

2. Direct the edges of G so that s is the only source, t is the only sink, and the resulting digraph is acyclic.

3. Compute a topological numbering Y for G.

4. Compute the directed planar dual G∗ = (V ∗, E∗) of G.

5. Compute a topological numbering X for G∗.

6. For each vertex u, let ωu be the line segment [(X(lef t(u)),Y (u)), (X(right(u)) − 1,Y (u))].

7. For each edge e = (u, v), let λe be the line segment [(X(lef t(e)),Y (u)), (X(lef t(e)),Y (v))].

Step 2 can be implemented by a simple variation on the depth-first-search method, based on a biconnectivity algorithm.

There are many kinds of topological numberings for acyclic digraphs: for example, one can define Z(u) to be the number of edges in the longest path from the source s to u. Any of these methods can be used in steps 3 and 5.

THEOREM 46.8 (Tamassia and Tollis [34]; Rosenstiehl and Tarjan [32]) A visibility representation of a biconnected planar graph with area O(n) × O(n) can be computed in linear time.

Proof We need to show that the drawing defined by ω and λ in Algorithm Bar Visibility satisfies the four properties P1, P2, P3 and P4 above.

First consider P1, and suppose that u and ul are two vertices of G. If Y (u) /= Y (ul) then ωu has empty intersection with ωul and so P1 holds. Now suppose that Y (u) = Y (ul).

Since Y is a topological numbering of G, it follows that there is no directed path in between u and ul (in either direction). Thus, from Lemma 46.5, in G∗ either there is a directed path from right(u) to lef t(ul) or a directed path from right(ul) to lef t(u). The first case implies that X(right(u)) < X (lef t(ul), so that the whole of ωu is to the left of ωul ; the second case implies that the whole of ωul is to the left of ωu. This implies P1.

Now consider P2, and suppose that e = (u, v) and el = (ul, vl) are edges of G, and denote lef t(e) by f and lef t(el) by f l. If X(f ) /= X(f l) then λe cannot intersect λel and P2 holds.

Now suppose that X(f ) = X(f l); thus in G∗ there is no directed path between f and f l.

It follows from Lemma 46.3 that in G either there is a directed path from the sink tf of f to the source sf l of f l, or a directed path from the sink tf l of f l to the source sf of f . In the first case we have Y (tf ) < Y (sf l ). Also, since e is on f and el is on f l, we have Y (v) ≤ Y (tf ) and Y (sf l ) ≤ Y (ul); thus Y (v) < Y (ul) and λe cannot intersect λel . The second case is similar and so P2 holds.

A similar argument shows that P3 holds.

Property P4 follows form the simple observation that for any edge e = (u, v), X(lef t(u)) ≤ X(lef t(e)) ≤ X(right(u)).

The drawing has dimensions maxvf ∈V ∗ X(vf ) × maxu∈V Y (u), which is O(n) × O(n).

It is easy to see that each step can be implemented in linear time.

Bar Visibility Representations and Layered Drawings

A graph in which the nodes are constrained to specified y coordinates, as in Figure 46.3, is called a layered graph. More precisely, a layered graph consists of a directed graph G = (V, E) as well as a topological numbering L of G. We say that L(u) is the layer of u. A drawing of G that satisfies the layering constraint, that is, the y coordinate of u is L(u) for each u ∈ V , is called a layered drawing. Drawing algorithms for layered graphs have been extensively explored [8].

A layered graph is planar (sometimes called h-planar) if it can be drawn with no edge crossings, subject to the layering constraint. Note that underlying the prerequisite Fig- ure 46.3 is a planar graph; however, as a layered graph, it is not planar. The theory of planarity for layered graphs has received some attention; see [11, 13, 19, 24].

If a planar layered graph has one source and one sink, then it is a planar st-graph. Clearly the source s has L(s) = minu∈V Lu and the sink t has L(t) = maxv∈V Lv . Since the layers define a topological numbering of the graph, application of Algorithm Bar Visibility yields a visibility representation that satisfies the layering constraints. Further, this can be used to construct a graph drawing by using simple local transformations, illustrated in Figure 46.15.

The following theorem is immediate.

THEOREM 46.9 If G is a planar layered graph then we can construct a planar layered drawing of G in linear time, with the following properties:

• There are at most two bends in each edge.

• The area is O(n) × O(n).

Although Algorithm Bar Visibility produces the visibility representation with good resolution, it may not produce minimum area drawings. Lin and Eades [24] give a linear time variation on Algorithm Bar Visibility that, for a fixed embedding, maximizes resolution. The algorithm works by using a topological numbering for the dual computed from a dependency relation between the edges.

Bar Visibility Representations for Orthogonal Drawings

An orthogonal drawing of a graph G has each vertex represented as a point and each edge represented by a polyline whose line segments are parallel to a coordinate axis. An orthogonal drawing of the 3-cube is in Figure 46.16.

It is clear that a graph that has a planar orthogonal drawing, has maximum degree of G at most 4. Conversely, one can obtain a planar orthogonal drawing of a planar graph with maximum degree at most 4 from a visibility representation by using a simple set of local transformations, described in Figure 46.17.

Figure 46.16 can be obtained from Figure 46.13 by applying transformation (c) in Fig- ure 46.17 to the source and sink, and applying transformation (d) to each other vertex.

Note that the transformations involve the introduction of a few bends in each edge. The worst case is for where a transformation introduces two bends near a vertex; this may occur at each end of an edge, and thus may introduce 4 bends into an edge.

THEOREM 46.10 If G is a planar graph then we can construct a planar orthogonal drawing of G in linear time, with the following properties:

• There are at most four bends in each edge.

• The area is O(n) × O(n).

In fact, a variation of Algorithm Visibility together with a careful application of some transformations along the lines of those in Figure 46.17 can ensure that the resulting drawing has a total of at most 2n + 4 bends, where n is the number of vertices; see [8].