Drawing Graphs:Introduction and Preliminaries

Introduction

Graph Drawing (see Chapter 4 for an introduction to graphs) is the art of making pictures of relationships. For example, consider the social network defined in Table 46.1. This table expresses the “has-written-a-joint-paper-with” relation for a small academic community.

It is easier to understand this social network if we draw it. A drawing is in Figure 46.1(a); a better drawing is in Figure 46.1(b). The challenge for Graph Drawing is to automatically create good drawings of graphs such as in Figure 46.1(b), starting with tables such as in Table 46.1.

The criteria of a good drawing of a graph have been the subject of a great deal of attention (see, for example, [3, 29, 30]). The four criteria below are among the most commonly used criteria.

• Edge crossings should be avoided. Human tests clearly indicate that edge crossings inhibit the readability of the graph [30]. Figure 46.1(a) has 6 edge crossings, and Figure 46.1(b) has none; this is the main reason that Figure 46.1(b) is more readable than Figure 46.1(a). The algorithms presented in this chapter deal with planar drawings, that is, drawings with no edge crossings.

• The resolution of a graph drawing should be as large as possible. There are several ways to define the intuitive concept of resolution; the simplest is the vertex resolution, that is, the ratio of the minimum distance between a pair of vertices to the maximum distance between a pair of vertices. High resolution helps readability because it allows a larger font size to be used in the textual labels on vertices. In practice it can be easier to measure the area of the drawing, given that the minimum distance between a pair of vertices is one. If the vertices in Figure 46.1 are on an integer grid, then the drawing is 4 units by 2 units, for both (a) and (b). Thus the vertex resolution is 1/2√5 "" 0.2236, and the area is  8. One can refine the concept of resolution to define edge resolution and angular resolution.

• The symmetry of the drawing should be maximized. Symmetry conveys the structure of a graph, and Graph Theory textbooks commonly use drawings that are as symmetric as possible. Intuitively, Figure 46.1(b) displays more symmetry than Figure 46.1(a). A refined concept of symmetry display is presented in Section 46.4.

• Edge bends should be minimized. There is some empirical evidence to suggest that bends inhibit readability. In Figure 46.1(a), three edges contain bends and eleven are straight lines; in total, there are seven edge bends. much better: all edges are straight lines.

Figure 46.1(b) is Each of these criteria can be measured. Thus Graph Drawing problems are commonly stated as optimization problems: given a graph G, we need to find a drawing of G for which one or more of these measures are optimal. These optimization problems are usually NP-complete.

In most cases it is not possible to optimize one of the criteria above without compromise on another. For example, the graph in Figure 46.2(a) has 8 symmetries but one edge crossing. It is possible to draw this graph without edge crossings, but in this case we can only get 6 symmetries, as in Figure 46.2(b).

The optimization problem may be constrained. For example, consider a graph representing prerequisite dependencies between the units in a course, as in Figure 46.3; in this case, the y coordinate of a unit depends on the semester in which the unit ought to be taken.

Graph Drawing has a long history in Mathematics, perhaps beginning with the theorem of Wagner that every planar graph can be drawn with straight line edges [38]. The importance of graph drawing algorithms was noted early in the history of Computer Science (note the paper of Knuth on drawing flowcharts, in 1960 [23], and the software developed by Read in the 1970s [31]). In the 1980s, the availability of graphics workstations spawned a broad interest in visualization in general and in graph visualization in particular. The field became mature in the mid 1990s with a conference series (for example, see [15]), some books [8, 22, 33], and widely available software (see [20]).

In this Chapter we briefly describe just a few of the many graph available drawing algorithms. Section 46.3 presents some algorithms to draw planar graphs with straight line edges and convex faces. Section 46.4 describes two algorithms that can be used to construct planar symmetric drawings. Section 46.5 presents a method for constructing “visibility” representations of planar graphs, and shows how this method can be used to construct drawings with few bends and reasonable resolution.

Preliminaries

Basic concepts of mathematical Graph Theory are described in [4]. In this section we define mathematical notions that are used in many Graph Drawing algorithms.

A drawing D of a graph G = (V, E) assigns a location D(u) ∈ R2 for every vertex u ∈ V and a curve D(e) in R2 for every edge e ∈ E such that if e = (u, v) then the curve D(e) has endpoints D(u) and D(v). If D(u) has integer coordinates for each vertex u, then D is a grid drawing. If the curve D(e) is a straight line segment for each edge e, then D is a straight line drawing.

For convenience we often identify the vertex u with its location D(u), and the edge e with its corresponding curve D(e); for example, when we say “the edge e crosses the edge f ”, strictly speaking we should say “the curve D(e) crosses the curve D(f )”.

A graph drawing is planar if adjacent edges intersect only at their common endpoint, and no two nonadjacent edges intersect. A graph is planar if it has a planar drawing. Planarity is a central concern of Graph Theory, Graph Algorithms, and especially Graph Drawing; see [4].

A planar drawing of a graph divides the plane into regions called faces. One face is unbounded; this is the outside face. Two faces are adjacent if they share a common edge. The graph G together its faces and the adjacency relationship between the faces is a plane graph. The graph whose vertices are the faces of a plane graph G and whose edges are the adjacency relationships between faces is the planar dual, or just dual, of G. A graph and its planar dual are in Figure 46.4.

The neighborhood N (u) of a vertex u is the list of vertices that are adjacent to u. If G is a plane graph, then N (u) is given in the clockwise circular ordering about u.