Drawing graphs using modular decomposition
Charis Papadopoulos
Department of Informatics University of Bergen http://www.ii.uib.no/∼charis
charis@ii.uib.no
Costas Voglis
Department of Computer Science University of Ioannina http://www.cs.uoi.gr/∼voglis
voglis@cs.uoi.gr
Abstract
In this paper we present an algorithm for drawing an undirected graph G that takes advantage of the structure of the modular decomposition tree of G. Specifically, our algorithm works by traversing the modular decomposition tree of the input graphGonnvertices andmedges in a bottom-up fashion until it reaches the root of the tree, while at the same time intermediate drawings are computed. In order to achieve aestheti- cally pleasing results, we use grid and circular placement techniques, and utilize an appropriate modification of a well-known spring embedder al- gorithm. It turns out, that for some classes of graphs, our algorithm runs inO(n+m) time, while in general, the running time is bounded in terms of the processing time of the spring embedder algorithm. The result is a drawing that reveals the structure of the graph Gand preserves certain aesthetic criteria.
Article Type Communicated by Submitted Revised Regular paper P. Eades and P. Healy January 2006 January 2007
This work is supported by the Research Council of Norway through grant 166429/V30 and co-funded by the European Union in the framework of the project “Support of Computer Science Studies in the University of Ioannina” of the “Operational Program for Education and Initial Vocational Training” of the 3rd Community Support Frame- work of the Hellenic Ministry of Education, funded by national sources and by the European Social Fund (ESF)
1 Introduction
The problem of automatically generating a clear and readable layout of complex structures inside a graph is receiving increasing attention in the literature [9]. In this work we present a drawing algorithm that takes advantage of the modular decomposition of a graph. Our goal is to highlight the global structure of the graph and reveal the regular structures within it. The usage of the modular decomposition has been considered by many authors in the past to efficiently solve other algorithmic problems [5, 1, 6, 20, 19].
Our approach takes advantage of the modular decomposition of the input graphG, which is a recursive tree-like partition that revealsmodules ofG, i.e., sets of vertices having the same neighborhood. By exploiting the properties of these modules and especially the properties of the modular decomposition tree T(G), we are able to draw the modules separately using different techniques for each one. To achieve aesthetically pleasing results, we utilize a grid place- ment technique, a circular drawing paradigm, and a modification of a spring embedder method, on the appropriate modules. Our algorithm relies on cre- ating intermediate drawings in a systematic fashion by traversing the modular decomposition tree of the input graph from bottom to top, while at the same time certain parameters are appropriately updated. In the end, the drawing of the graphGis obtained by traversingT(G) from the root to the leaves, in order to compute the final coordinates of the vertices in the drawing area, using the parameters computed in the previous traversal ofT(G). It turns out that this way of processing T(G) enables us to visualize the graph in various levels of abstraction.
Many techniques for drawing hierarchical clustered graphs deal with a graph and its tree representation [2, 11, 12, 15, 17, 27, 34, 35]. All these methods address the problem of visualization, by drawing the non-leaf nodes of the tree as simple closed curves. Brandenburg [2] uses an underlying tree-like structure of a graph in order to layout graph grammars. Force directed methods have also been developed to support and show the structure of a clustered graph that is a 2-level decomposition scheme [24, 39]. Also, in [27, 28], the drawing of a clustered graph is considered as a problem of avoiding overlapping vertices with non-uniform size. So far in the literature, two main classes of solutions to the non-uniform vertex overlapping problem exist: the layout adjustment algorithms [13, 21, 23, 29], which are post-processing approaches employed after a final layout is generated, and the force-integration approaches [22, 28, 37, 39], where overlapping is avoided at the same time the layout is created, by a force directed algorithm. This is achieved by modifying the attractive and repulsive forces of the existing methods. Related to modular decomposition there is an algorithm for generating drawings of directed graphs based on a specific parse tree [34, 35]. It is important to note that the approach for the directed graphs apply only on certain digraphs which are decomposed by two different operations (known as series and parallel) [34].
The theory of modular decomposition originates from Gallai’s work for com- puting a transitive orientation [20]. Modular decomposition is also known assub-
stitution decomposition, X-join decomposition, and clan decomposition. There has been an increasing interest for designing a simple and fast algorithm for computing the modular decomposition of a graph [7, 8, 14, 31, 32]. Some of the linear-time algorithms that use different approaches are given by [8, 31].
Quite recently it has been proposed a linear-time algorithm for computing the modular decomposition of a directed graph [30]. A great number of NP-hard optimization problems can be efficiently solved if a solution for the decomposed subgraphs is known by using modular decomposition. To name a few of them we refer to the problem of computing the treewidth and the minimum fill-in [1].
Moreover it has been proposed to obtain efficient algorithms by expressing op- timization problems in monadic second-order logic [6]. Other application areas of modular decomposition arise in biological clustering of proteins [19].
To achieve aesthetically pleasing results, our algorithm utilizes a grid place- ment technique, a circular drawing paradigm, and a modification of a spring embedder method, on the appropriate modules. It turns out that our draw- ing methods must take into account the size of non-uniform vertices. Under this constraint, we propose a modified spring embedder algorithm that falls in the category of force-integration approaches. Vertex-to-vertex overlapping is avoided by applying vertex size constraints gradually and by introducing a reducing factor, based on the density of the input graph, that acts on the attrac- tive forces between vertices. We note that considering other aesthetic criteria, such as the number of vertex-to-edge crossings, would conflict with our basic goal of the exposal of desired subgraphs.
In addition, there are cases in which the final drawing of our algorithm takes time linear in the size of the input graph. This arises from the fact that certain classes of graphs have been considered by many authors in the past (see [5]), who explored the structural and algorithmic properties of their modular decomposition trees. It follows that the structure of their trees ensures that each tree node can be processed in time linear in the size of the given part of the tree. Thus, since T(G) can be constructed in time linear in the size of the graph G [8, 31], the processing of the entire modular decomposition tree and consequently its drawing takes time linear in the size of the input graph.
Furthermore, our drawing algorithm highlights the global structure of the graph and reveals the regular structures inside the graph.
However in some cases the algorithm produces some unnecessary edge cross- ings and vertex-to-edge overlapping since it tries to display the symmetry of vertices being in the same module. For that purpose we slightly modify our basic algorithm and propose an alternative drawing approach that takes the vertex-to-edge crossings into account. We achieve this by relaxing certain con- strains that used to hold together all the vertices of a module. Although the readability of the new drawing is being improved (in the sense of less edge crossings), the symmetry of certain subgraphs is relegated. Therefore we pro- pose both algorithms in order to achieve the goal of exposing regular structures and the ability of reading a clear drawing of a graph.
Our work is organized as follows. In Section 2 we establish the notation and related terminology and we present background results. In particular, we show
structural properties of a unique tree representation of a graph and establish our drawing conventions with respect to the tree representation. In Section 3, we describe our drawing algorithm, while in Section 4 we propose a modification of a spring embedder algorithm and give their efficient analysis for a given graph. In Section 5 we compute the time complexity of our algorithm and show that the drawings of some classes of graphs can be computed in linear time. Section 6 presents some examples of graphs computed by our drawing algorithm. In Section 7 we slightly modify the algorithm and propose another drawing approach, and, finally, in Section 8 we conclude our work and discuss possible future extensions.
2 Preliminaries
We consider finite undirected graphs with no loops or multiple edges. For a graph G, we denote byV(G) and E(G) the vertex set and the edge set of G, respectively. Let S be a subset of the vertex set of a graph G. Then, the subgraph ofGinduced by S is denoted byG[S]. A clique is a set of pairwise adjacent vertices. The degree of a vertex x in the graph G, denoted d(x), is the number of edges incident onx. For a graphGonn vertices andmedges, D(G) = 2m/n is the average degree of G. The complement of a graph G is denoted byG.
Let T be a rooted tree. For convenience, we refer to a vertex of a tree as a node. The parent of a nodet of T is denoted byp(t), whereas the node set containing the children oftinT is denoted bych(t). Lethbe the height of the tree T. Then, we denote by Li the node set containing the nodes of the i-th level ofT, for 0≤i≤hwhere the root is at level 0.
2.1 Modular Decomposition
A subset M of vertices of a graph G is said to be a module of G, if every vertex outside M is either adjacent to all vertices in M or to none of them.
The emptyset, the singletons, and the vertex setV(G) aretrivialmodules and wheneverG has only trivial modules it is called a prime (or indecomposable) graph. It is easy to see that the chordless path on four vertices,P4, is a smallest non-trivial prime graph, since graphs with three vertices are decomposable [5].
A non-trivial module is also calledhomogeneous set. A moduleM of the graphG is called astrong module, if for any moduleM′ 6=M ofG, eitherM′∩M =∅ or one module is included into the other. LetM be a module of a graphG. If G[M] is a disconnected graph, thenM is called aparallel module. IfG[M] is a disconnected graph, thenM is called aseries module. If bothG[M] andG[M] are connected graphs, thenM is called aneighborhood module.
Themodular decompositionof a graphGis a linear-space representation of all the partitions ofV(G) where each partition class is a module. Themodular decomposition treeT(G) of the graphG(ormd-treefor short) is a unique labelled tree associated with the modular decomposition ofGin which the leaves ofT(G)
are the vertices ofG and the set of leaves associated with the subtree rooted at an internal node induces a strong module of G. Thus, the md-tree T(G) represents all the strong modules ofG. An internal node is labelled by eitherP (for parallel module),S (for series module), orN (for neighborhood module).
It is shown that for every graph G on n vertices and m edges, the md-tree T(G) is unique up to isomorphism, the number of nodes inT(G) isO(n) and it can be constructed inO(n+m) time [8, 31]. More details about the modular decomposition of a graph can be found in [7, 8, 14, 31, 32].
Lettbe an internal node of the md-treeT(G) of a graphG. We denote by M(t) the module corresponding to t, which consists of the set of vertices ofG associated with the subtree ofT(G) rooted at nodet; note thatM(t) is a strong module for every (internal or leaf) node t of T(G). Let t1, t2, . . . , tp be the children of the node tof md-tree T(G). We denote byG(t) therepresentative graphof nodetdefined as follows: V(G(t)) ={t1, t2, . . . , tp}andtitj ∈E(G(t)) if there exists edge vkvℓ ∈ E(G) such that vk ∈ M(ti) and vℓ ∈ M(tj). For the P-, S-, and N-nodes, it is easy to see that the following lemma holds by definition (see also Proposition 18 in [6] and Theorem 2.2 in [31]).
Lemma 2.1. Let Gbe a graph,T(G)its modular decomposition tree, and tan internal node ofT(G). Then,G(t)is an edgeless graph iftis a P-node, G(t)is a complete graph ift is an S-node, andG(t)is a prime graph ift is an N-node.
In Figure 1 we show a graphGon 14 vertices and its modular decomposition tree T(G). Since G is disconnected, the root (node t1) of T(G) is a P-node.
The graphs G[M(t2)] and G[M(t3)] are the two connected components of G which are shown on the left and right side, respectively, in Figure 1(a). Their representative graphsG(t2) andG(t3) consist of 4 (=|ch(t2)|) and 7 (=|ch(t3)|) vertices, respectively.
In general, using modular decomposition for solving a problem can be quite challenging. A great number of NP-hard optimization problems, such as weighted maximum clique and coloring, can be easily solved if a solution is known for ev- ery representative graph in the modular decomposition tree. A typical algorithm for exploiting the modular decomposition often has the following structure (see for example [1] and [6]). First, the algorithm computes the modular decom- position tree T(G) of the input graph G using one of the known linear-time algorithms [8, 30, 31]; then, in a bottom-up fashion, the algorithm computes for each nodet ofT(G) the optimal value for the subgraph G[M(t)] of Ginduced by the set of all leaves of the subtree ofT(G) rooted att. Thus, the compu- tation starts by assigning the optimal value to the leaves. Then the algorithm computes the optimal value of each interior nodetby using the optimal values of all the children oft depending on the type of the node. Finally the optimal value of the root is the optimal value of the problem for the input graphG.
Thus to specify such a modular decomposition based algorithm we only have to describe how to obtain the value for the leaves and which formula to evaluate or which subproblem to solve on P-nodes, S-nodes, and N-nodes using the values of all children as input (see for an exposition [5]). In the present work we utilize a modular decomposition based algorithm to draw arbitrary graphs, combined
11
12
14 13
10 1
2
3 7
4
6 5
9 8
(a)
11 12
14 13
10 7
3 4
6 2
8 9
1 5
P
S
P P P
N
t1
t2 t3
t4 t5 t6
(b)
Figure 1: (a) A graphGand (b) its modular decomposition treeT(G).
to well known drawing techniques such as circular drawings and force directed methods.
2.2 Modular Decomposition Based Drawing
Our drawing algorithm is based on the modular decomposition tree of a given graph G. We deal with box-shaped vertices with a specific size. For every t∈T(G) we definec(t) = (x(t), y(t))∈R2 to be the coordinates of the center of nodet, andb(t) = (w(t), h(t))∈R2 to be the dimensions of the box of node t, where w(t) and h(t) are the width and the height of the box, respectively.
In other words, c(t) is the center of the box b(t). We adopt the straight-line drawing convention and we impose the following constraints:
C1 vertices do not overlap;
C2 vertices in every strong module M(t), induced by an internal node t of T(G), are drawn close (in terms of their Euclidean distance) to each other;
C3 vertices in every strong module M(t), induced by an internal node t of T(G), are drawn according to the structure (edgeless or complete or prime) of the representative graphG(t);
Observe that we do not consider other aesthetic criteria that are applied commonly in graph drawing algorithms such as the constraint of no vertex- to-edge crossing [9]. The reason is that constraints C1–C3 tend to produce drawings of graphs that reveal the structures of the induced modules. On the other hand classical constraints may be useful in terms of general readability of a drawing, but they cancel the expository properties of C1–C3. A natural technique is to incorporate both kinds of criteria with the best possible manner so that the output drawing exposes important structures while at the same time certain aesthetic criteria are satisfied. However the criteria C1–C3 are somehow incompatible with other aesthetic criteria in the sense that a group of vertices (module) cannot be spread in the layout. Therefore we put as a primary goal the achievement of C1–C3 and we also propose an alternative drawing approach that tries to incorporate other aesthetic criteria.
Definition 2.1. A drawing with the previous constraints is called a modular decomposition based drawing (or md-drawing for short) Γ(G) of the graph G which is a mapping between the vertices and the Euclidean spaceR2: Γ(G) : V(G)→R2.
Our problem is to produce a drawing Γ(G) for a given graphGwith non- uniform, box-shaped vertices. Clearly Γ(G) = Γ(G[M(root)]). To produce the final drawing, our algorithm needs to compute a drawing based on the representative graphG(t), for every internal nodet∈T(G).
Definition 2.2. Arelative drawing Γ′(t, T(G)) is an md-drawing of the repre- sentative graphG(t).
We mention that the frame boundaries of a drawing are the horizontal and vertical sides of the smallest rectangle that covers the drawing. The frame boundaries of a relative drawing Γ′(t, T(G)), define the dimensions of the box b(t) of nodet.
2.3 Modular Decomposition as a Clustering Technique
Modular decomposition can be thought as a quite effective clustering technique, that aligns naturally with graph drawing notions, since it clusters vertices with the same neighborhood. This is even more evident if we compare modular decomposition to previous suggestions that were either too specialized (i.e., partition into cycle of cliques [3]), too broad (biconnected components [9]) or too heuristic (i.e., structural clustering [25]). It is also of great importance that we suggest a technique that automatically creates and draws clusters, in opposition to other drawing methods that are applied on an already clustered graph.
A useful insight on qualifying tree-like decompositions is given in [16]. This work presents some design criteria that should be fulfilled by the decomposi- tion trees so that graph visualization applications can substantially benefit from their usage. Two of the general clustering criteria are that good decompositions should (i) exhibit a strong relationship between vertices in the same cluster and (ii) preserve the relevant connectivity properties of the graph, so that the viewer can grasp them even observing a contraction of it. Modular decomposition sat- isfies both these criteria, because a cluster (module) consists of vertices having the same neighborhood. We note that for directed graphs the usage of the corresponding modular decomposition achieves both goals as shown in previous works [34, 35].
Finally, other clustering techniques [25] may not preserve the information of the graph in various levels of contractions. The representative graph of an arbitrary clustered graph, also known as the quotient graph [8, 25], results by contracting all clusters into single nodes. Notice that an edge in the quotient graph may represent few edges from the original graph connecting some ver- tices which belong in different clusters. Thus, by examining the representative graph of clusters computed with any arbitrary manner, one looses information about the connectivity of the graph. On the other hand in modular decomposi- tion based clustering if two nodes, which represent a contraction of two clusters (modules) are connected, then all the vertices of these clusters are also con- nected. In this way there is no loss of information by examining the edges of the representative graph obtained by contracting the modules of the graph (see also [34]).
3 The Algorithm
Let G be a graph on n vertices v1, v2, . . . , vn with non-uniform dimensions b(v1), b(v2), . . . , b(vn), respectively, andmedges. Our algorithm first computes the md-treeT(G) using one of the known linear-time algorithms [8, 31]. For every internal nodet ∈T(G) we perform an initialization step, by setting its box dimensions to zero. We recall that the boxes of the leaves ofT(G) have predefined dimensions, since they are the vertices ofG. In this step, we also set the center of every nodet∈T(G) to zero.
In bottom-up fashion, we traverse the md-treeT(G) and calculate the rela- tive drawing Γ′(t, T) for every internal nodet. More precisely, according to the type of nodet(P or S or N) we apply a specific drawing algorithm to layout all the children oft, using the representative graphG(t); recall thatG(t) is either an edgeless, or a complete, or a prime graph. This relative drawing modifies the coordinates of the centerc(ti) for every nodeti∈ch(t), taking into account the dimensions of the non-uniform boxesb(ti). This implies that only the children oft obtain the new coordinates according to the relative drawing. In order to apply the new coordinates to the subtree rooted at t, and finally to the graph G[M(t)], we store the displacements from the previous coordinates,dis(ti) for every ti. We usedis(ti) to update the coordinates of the vertices of G[M(t)]
in a later step. In addition, we update the dimensions of the box of nodet in proportion to the frame boundaries of the relative drawing Γ′(t, T).
Finally, we traverse the md-tree T(G) in a top-down fashion and for every internal nodet ∈ T(G), we add the displacement dis(t) to the centers of the boxes of every child node ti ∈ ch(t). In this way, all the vertices of G[M(t)]
obtain the right coordinates relative to the center of their ancestor nodet. Thus, the final output drawing Γ(G) ofG, is Γ(G[M(root)]).
We mention that every relative drawing uses a predefined constantki as the preferred edge length of the drawing at the level setLi, 0 ≤i ≤h−1, of the md-treeT(G). Two approaches can be considered regarding the preferred edge lengthski. In the first, allki hold the same value and in the second,ki vary as an inversely proportional function ofi(see also [38]). With the second approach, each module of G can be drawn further apart and can be distinguished more clearly, whereas with the first approach more compact drawings are created.
The algorithm, called Module Drawing, is given in detail in Algorithm 1.
We note that the preferred edge lengths ki are global variables. The relative drawings are done by means of three functions, namely,Draw Edgeless, which is applied on a P-node,Draw Complete, which is applied on a S-node, andDraw- Prime, which is applied on a N-node. Recall that the leaves of T(G) are the vertices ofG.
AlgorithmModule Drawing
Input: A graphGonnvertices andmedges.
Output: An md-drawing Γ(G) of the graphG.
1. Construct the modular decomposition treeT of the graphG;
2. Initialize the centersc(t)←(0,0) for everyt∈T and setb(t)←(0,0) for every internal nodet∈T;
3. Compute the node sets L0, L1, . . . , Lhof the levels 0,1, . . . , hofT, and assign values to the preferred edge lengthski;
4. for i=h−1 down to 0 do { bottom-up fashion}
for every internal nodet∈Li do
4.1 if tis a P-node then Γ′(t, T)←Draw Edgeless(t, T);
4.2 else iftis an S-nodethenΓ′(t, T)←Draw Complete(t, T);
4.3 else {t is an N-node} Γ′(t, T)←Draw-Prime(t, T);
4.4 Compute the displacementdis(ti), for each nodeti∈ch(t), with respect to the previous placement;
4.5 Update the size of the rectangle boxb(t), according to the frame boundaries of Γ′(t, T);
5. for i= 0 down toh−1 do { top-down fashion}
for every internal nodet∈Li do
for every childti∈ch(t) doc(ti)←c(ti) +dis(t);
6. Return the drawing Γ(G) = Γ′(r, T) computed in the rootrofT;
Algorithm 1: Module Drawing.
The formal descriptions of functionsDraw Edgeless andDraw Completeare given below whereas the functionDraw-Primeis described in detail in Section 4.
All these functions are aware of the preferred edge length, denoted byk, which may be different for each level ofT(G). We note here, that one can use different drawing techniques for each relative drawing to fulfill desired aesthetic criteria.
Our approach draws edgeless graphs on an underlying grid, complete graphs in a circular way, and prime graphs using a spring embedder method. We point out that there are other well known techniques for drawing the nodes (intermediate drawings) of the tree, such as the inclusion tree layout convention [27] or more general the floor-planning approach used in VLSI design [26]. Although these approaches can be applied in order to produce the final drawing of the graph, we choose the technique described in Algorithm Module Drawing for clarity and simplicity reasons.
3.1 Function Draw Edgeless
Vertices are placed by function Draw Edgeless, keeping in mind that there are no connecting edges between them. This is achieved by a grid placement of the nodes in an arbitrary order. Since the nodes have non-uniform sizes, the task of minimizing the drawing area is NP-hard by the two dimensional bin packing problem [27]. A way to avoid this is to allow only two possible arrangements of the nodes, either horizontal or vertical. In [27] this restricted problem is solved in polynomial time by using a dynamic programming approach. Here we do not allow this restriction and propose a simple algorithm for the grid placement of the nodes, even though one can easily apply the approach of [27] whenever the problem of minimizing the drawing area is primary.
The approach that we propose is quite simple. The Euclidean distance be- tween the boundaries of two nodes placed adjacent on the grid is at leastk. For symmetry reasons, we distribute evenly the space between the nodes in each row, so that a complete alignment is achieved. Each row is then processed one by one and it is placed below the previous one, keeping distance of at leastk from the bottom boundary of the previous row. The function Draw Edgeless is given in details below.
FunctionDraw Edgeless(t, T) 1. Set r =lp
|ch(t)|m
,c =lp
|ch(t)|m
and define a grid F ofr rows and c columns;
2. For everytl∈ch(t), maptl in arbitrary order, to be at positionF(i, j);
3. for every rowiofF do
3.1 For everytl mapped in row i, set y(tl) = 0 andx(tl) such that the shortest horizontal distance between the boundaries of the neighbor- hood boxes isk.
t1 t2 t3 t4
t5 t6 t7 t8
t9 t10 t11
t12
t13 t14
h1
h2
h3
h4
}k
wmax
z }| {
Figure 2: Illustrating Function Draw Edgeless.
3.2 Set wi= (c−1)·k+ X
tl∈rowi
w(tl) and hi= max
tl∈rowi(h(tl));
4. Set wmax= max(wi);
5. for i= 2 tor do
5.1 For everytl mapped in rowi ofF, updatex(tl) such that the total length of rowibe wmax;
5.2 For everytlmapped in rowiofF, updatey(tl) such that the shortest vertical distance between the neighborhood rows of heighthi−1 and hi+1 isk;
6. Return Γ′(t, T), containing the centersc(tl) for everytl∈ch(t);
In Figure 2 we illustrate the output of function Draw Edgeless on 14 dis- connected vertices with non-uniform sizes, using preferred edge lengthk= 30.
The algorithm computes a gridF of 4 rows and 4 columns. In Step 3 of func- tion Draw Edgeless, the quantitiesh1, h2, h3, h4 are computed according to the height of the vertices of each row. Also in Step 4 the quantitywmax is set as the maximum length, among the 4 rows ofF. Note that, in the last row of the grid, verticest13 andt14 are aligned left and right, respectively.
3.2 Function Draw Complete
Function Draw Complete is basically a circular drawing algorithm, eventhough the representative graph G(t) is a complete graph. We have chosen to draw complete graphs in this way, in order to expose the structure of a series module (see constraint C3). Furthermore, a circular drawing satisfies the aesthetic criterion of symmetry and is the usual way of representing complete graphs in textbooks.
Six and Tolis [36] proposed an approach for placing group of vertices in a circular way so that the number of edge crossings is low. Their algorithm is based on a force-directed technique and requires at leastn2 steps for a graph onnvertices. However in our case all edges between the corresponding group of vertices (modules) are present, sinceG(t) is a complete graph. Thus we do not seek to achieve a drawing with low number of edge crossings withinG(t), since we focus on the close placement of the vertices ofG(t) and the ability of distinguishing the property ofG(t) being a complete graph. Next we present a quite simple deterministic algorithm for placing non-uniform sized vertices in a circular way that runs inO(n) time and without the knowledge of the edges of the graph.
The vertices of the series module are placed in an arbitrary order on equal arcs, on the circumference of a cycle centered atc(t). The initial radius is de- termined by the smallest sized box. More specifically, function Draw Complete process each nodeti ∈ch(t) one by one. It computes a valuef(ti) that repre- sents the maximum distance from the center c(ti) of the boxb(ti), to a point on its boundary. We usef(ti) to determine the distance between two adjacent vertices in the circle, in the following way. For every vertexti we calculate two radiuses r1 and r2 that define two concentric circles centered at c(t). In the circle defined by r1, vertexti and its previous ti−1 are placed on a θ degrees arc, so that the minimum distance from their boundaries, is k. The radius r2
defines a circle whereti and ti+1 are placed in the same way. To prevent over- laps, we setr(ti) to be the maximum of these two radiuses. In the special case where the boxb(ti) ofti has the same dimensions with any of the two adjacent vertices in the circleC, we setr(ti) to be the radius defined by the equal sized box adjacent vertex. With this approach, we achieve that equal sized boxes are placed on the same circle, without any overlap, since the unequal sized vertex will be placed on a different circle. Finally, we draw every vertextion the circle defined by radiusr(ti), with angleθ. Obviously, for a complete graph with uni- form nodes the drawing is a perfect circle. The formal description of function Draw Complete is given in details below.
FunctionDraw Complete(t, T)
1. For every ti ∈ch(t) set f(ti) as the half of the length of the diagonal of boxb(ti);
2. Define a circle C on|ch(t)|vertices and setθ=|ch(t)|2π ;
3. For everyti∈ch(t) mapti in arbitrary order, on the circleC;
t1
t1
t2
t2
t3
t3 t4
t4
t5
t5
t6
t6
t7
t7
t8
t8
t9
t9
k t
r1
r2 r3
r4
| {z }
f(t8)
| {z }
f(t9)
(a) (b)
Figure 3: Illustrating Function Draw Complete.
4. for everyti∈ch(t) do
4.1. Setr1= f(ti2 sin (θ/2))+k+f(ti−1) and r2= f(ti2 sin (θ/2))+k+f(ti+1),
where ti−1 and ti+1 are the two adjacent vertices of ti in the circle C;
4.2. if b(ti) =b(ti−1) then r(ti) =r1; else if b(ti) =b(ti+1) then r(ti) =r2 ; else r(ti) = max(r1, r2);
5. For every ti ∈ch(t), put (calculate c(ti))ti on a circle, centered on c(t) with radiusr(ti);
6. Return Γ′(t, T), containing the centersc(ti) for every ti∈ch(t);
In Figure 3(a) we present an illustration of Draw Complete on 9 vertices with preferred edge length k = 30. The algorithm computes 4 different ra- diuses, according to the size of each box, namelyr1, r2, r3, r4. Note that ver- ticest2, t3, . . . , t7 are placed on a circle of radiusr1, since they have the same sizes. It is also clear, that each valuef(ti) defines a circumcircle around the boxb(ti) (see for examplef(t8), f(t9)). Figure 3(b) is the final relative drawing of the S-nodet, with 9 children. Remark that the representative graphG(t) is a complete graph.
For the time complexity of functions Draw Edgeless and Draw Complete, it is easy to see that the following lemma holds.
Lemma 3.1. Let T(G) be a modular decomposition tree of graph G and let ch(t) be the set of children of a P-node (resp. an S-node)t ∈T(G). Function Draw Edgeless (resp. Draw Complete) constructs a relative drawingΓ′(t, T)in O(|ch(t)|)time.
4 Modified Spring Embedder
In this section we describe in detail a spring embedder algorithm for the im- plementation of function Draw Prime. Recall that this function is applied on an N-node t ∈ T(G). Since the representative graph G(t) is a prime graph, function Draw Prime requires the vertex setV(G(t)) and the edge setE(G(t)).
The main task of Draw Prime is to combine the aesthetic properties of a spring embedder algorithm with the constraint that no vertex-to-vertex over- lapping occurs. The fact that Draw Prime is applied on the representative graph G(t) that contains vertices with non-uniform sizes, makes the drawing task more demanding.
The function Draw Prime falls in the category of force-integration approaches [28, 22]. It is based on the Fruchterman & Reingold (FR) spring embedder algo- rithm [18] and follows the general guidelines of Harel & Koren [22]. Draw Prime consists of a main iteration loop, that is repeated until some termination criteria are met. There are three basic steps to each iteration: (i) calculate the effect of the edge-attractive forces (ii) calculate the effect of vertex-to-vertex repulsive forces and (iii) limit the total displacement by a quantity called temperature which is decreased over the iterations. The temperature is decreased by acool- ing schedule, the choice of which greatly affects the quality of the drawing. To summarize, Draw Prime starts with an initial random placement of the vertices and an initial temperature, and performs the main iteration loop, until the un- derlying physical system reaches an equilibrium state. As presented in [18], we choose a two phase cooling scheme: the first phase starts with a constant initial temperature and reduces it using an exponential cooling scheme, and the sec- ond phase, which starts after a number of iterations, maintains a constant low temperature.
As already mentioned, we must take into account the size of the childrenti
of a nodetso that vertices ofG(t) would not overlap. To achieve this, we have modified the formulas for the attractive and the repulsive forces between the vertices of the graph. The final formulae for the forces will be presented later in the section. We will first describe the heuristics that we use to avoid overlapping.
According to [22], the first modification to the original FR algorithm will result the following formulae for the attractivefa and the repulsivefrforces:
F R: fa(rF R) =rF R2
k and fr(rF R) = k2 rF R
M odif ied F R: fa(rM F R) = r2M F R
k and fr(rM F R) = k2
max(rM F R, ǫ), where rF R = ||c(ti)−c(tj)||2, rM F R = f(ti, tj), and f(ti, tj) is the shortest
(a) (b)
Figure 4: Drawings of a graph using Modified FR forces (a) from the first iteration and (b) after the first 50 iterations.
distance between the boundaries of the boxesb(ti) andb(tj). The variablekis the preferred edge length for the drawing andǫis a small positive number.
The next extension is to impose the vertex size constraints gradually. Specif- ically, at the early iterations of our spring embedder the vertices of the prime graph are considered dimensionless, and thus, we use the forces of the FR algo- rithm. This policy, combined with a large initial temperature, allows the layout to escape possible local optimum states. In this way a possible cluttered lay- out is found at early stages of the algorithm, and then, we use the Modified FR repulsive and attractive forces to fully prevent overlaps (see also [22]). In Figure 4(a) we show a drawing example of a graph taken from [22] using only Modified FR attractive and repulsive forces and in Figure 4(b) we present a better layout of the same graph using our technique.
After thorough experimental testing we noticed that in many cases, and especially for some small choices of preferred edge lengthk, the results were not satisfactory. Vertex overlapping could not be avoided, since k was small with respect to the dimensions of the vertices. This defect appeared most frequently when the representative prime graph G(t) was dense. The reason is that the large number of attractive forces, combined with a small value of k, do not allow large vertices to be in a certain distance in order to avoid overlapping. To overcome this problem we decided to use a factorwin the calculation of the edge attractive forces, inversely proportional to the graph’s density. In this manner, we succeed in weakening edge attractive forces, and allowing the algorithm to position vertices without overlaps.
Hereafter we will denote by Gthe representative graph G(t). To compute the reducing factorw, we use the average degree D(G) that can be thought as a measure for the connectivity of G. To be more precise, we use D−1(G) as the factor in the Modified FR edge attractive force calculation fa. It follows that the use ofD−1(G) as a multiplicative factor weakens the attractive forces between vertices. Note that, since the smallest prime graph is aP4, for a prime
(a) (b)
Figure 5: Drawings of a 5×5 grid using (a)w=D−1(G) = 0.31 and (b)w= 1.
graphGwe have: 0< D−1(G)≤0.57.
So far, we have explained how the usage of D−1(G) will aid in the pro- cess of obtaining a better layout of dense graphs. However, when the graph is sparse, such an approach will lead to wasted drawing space, since vertices will be attracted by a small number (|E(G)|) of weak forces. To overcome this, after a certain point in the algorithm we use D(G) as the multiplicative fac- tor so that the final layout would be more compact. The distinction between sparse and dense graphs is rather vague. One approach is to put a threshold in the middle of the interval of the previous inequality ofD−1(G) and consider dense the graphsGsuch that D−1(G)<0.28 and sparse the graphs such that D−1(G) > 0.28. However this approach leads to a possible misjudgement of sparse and dense graphs, since there is no reason of such a uniform distribution of D−1(G). Another way is to choose a numberq, 1< q <2, and define the graph to be sparse if|E(G)|=O(|V(G)|q) [33]. Applying such a heuristic for distinguishing sparse and dense graphs gives the desired multiplicative factor for each corresponding case. Experimental results, lead us to use the multiplicative factor D−1(G) from the beginning, regardless whether the graph is sparse or dense. The reason is that this technique provides additional help to overcome possible local minimum states. Moreover it can be thought of as a heuristic in order to allow the drawing to occupy large drawing area at early iterations so that its structure has the ability to be unfolded by weakening forces. At final iterations we strengthen the attractive forces in order to reduce the area and achieve a more compact layout.
In Figure 5 we show two drawings of a 5×5 grid with random dimensioned vertices. The preferred edge length is set to k= 60, which is a small number with respect to the dimensions of the vertices. In Figure 5(a) the factor w = D−1(G) = 0.31 is used in the early iterations for the calculation of the attractive forces. We consider grid graphs to be sparse, which implies that the factor is
reversed (w = D(G)) at final iterations and, thus, the layout becomes more compact. In Figure 5(b) the multiplicative factorwis set to one in all iterations.
Having described the two main features of our spring embedder algorithm, we can present the attractive and repulsive forces of function Draw Prime (DP) as follows. We mention that the early and the final iterations coincide with the first and the second part of the cooling schedule, respectively.
DP : fa(rDP) = w·r2DP
k and fr(rDP) = k2
max(rDP, ǫ) (1) where,rDP =
||c(ti)−c(tj)||, at early iterations f(ti, tj), at final iterations
and w =
D−1(G), at early iterations D(G), at final iterations, and
if Gis sparse.
For the practical behavior of algorithm Draw Prime, it is crucial to discuss about the termination criteria. Commonly, the algorithm stops if it reaches a maximum number of iterations. Nevertheless, we use a heuristic to determine whether the drawing reached a state of minimum energy and the algorithm can be stopped. This heuristic is based on the total displacement of all the vertices at one main iteration.
In the j-thiteration we calculate the total displacementσ(j) for allti∈ch(t):
σ(j) = X
ti∈ch(t)
||s(ti)||2. (2)
Everyκiterations we compute the mean valueeσ(j, κ) of the differences of total displacement
e
σ(j, κ) = 1 κ
j+κ−1X
l=j
|σ(l+ 1)−σ(l)|. (3)
The algorithm stops if sc≡
σ(je +κ,2κ)−eσ(j, κ) eσ(j, κ)
< ǫ,
whereǫ <1 is small positive number. Quantityschas been extensively tested as a termination criterion with very promising results. In detail function Draw Prime is presented below.
FunctionDraw Prime(t, T)
1. while iterations≤maxiter do 1.1 for every vertexti∈V(G(t)) do
Set the displacements(ti) := 0;
for every vertextj6=ti∈V(G(t)) do
calculate the displacement s(ti) using the repulsive forcefr
between verticesti andtj as described in Equation (1);
1.2 for every edgetitj ∈E(G(t)) do
calculate the displacementss(ti), s(tj) using the attractive force fa
between verticesti andtj as described in Equation (1);
1.3 for every vertexti∈V(G(t)) do
calculate the coordinatesc(ti) using min (T, s(ti));
1.4 if convergence criterion is met then break;
1.5 if T ≤ Tmin then
if G(t) is dense then w= 1/w;
elsereduce the temperatureT;
2. Return Γ′(t, T), containing the centersc(ti) for every ti∈V(G(t));
We denote by ℓ the number of the main iterations needed by our spring embedder algorithm. Fruchterman & Reingold suggested thatℓis proportional to the size of the graph [18]. Tunkelang in his PhD thesis viewed ℓ as a lin- ear function of the number of vertices [37]. Since the second step inside the main iteration of Draw Prime requires |V(G)|2 operations, we conclude with the following lemma.
Lemma 4.1. LetT(G)be a modular decomposition tree of graphGand letch(t) be the set of children of an N-node t∈T(G). Function Draw Prime constructs a relative drawingΓ′(t, T)inO(ℓ· |ch(t)|2)time, whereℓis the number of main iterations that a spring embedder algorithm performs.
A faster drawing technique for prime graphs can be incorporated in our general framework of Algorithm Module Drawing, as long as it conforms with the following constraints: (i) takes node sizes into account and (ii) prevents overlaps, regardless of the preferred edge length.
5 Time Complexity
Next, we introduce the definition of the prime cost of a graph which we will need in our analysis. LetGbe a graph andT(G) be its modular decomposition tree. We denote byα(G) ={t1, t2, . . . , ts}the set of the N-nodes ofT(G). We define theprime cost ofGas the value
φ(G) = X
t∈α(G)
ℓ· |ch(t)|2,
wherech(t) denotes the set of children of nodet in T(G) andℓ is the number of iterations of the spring embedder.
It is not difficult to see that for any n-vertex graph G, we have φ(G) = O(ℓ·n2); for an n-vertex P4-free graph (also known as cograph) G we have φ(G) = 0, since its md-tree (also known as cotree) does not contain any N- node [5]. It follows that in other classes of graphs their prime cost is constant.
For example, any N-node of the md-tree of aP4-reducible graph1 contains at most five children [5]. Hence for an n-vertex P4-reducible graph G we have φ(G) =O(1). We notice that these classes of graphs arise in applications such as examination scheduling problems and semantic clustering of index terms [5].
Theorem 5.1. Let G be a graph onn vertices and m edges. Algorithm Mod- ule Drawing constructs an md-drawingΓ(G) in O(n+m+φ(G)) time, where φ(G)is the prime cost of the input graphG.
Proof. Step 1 of Module Drawing takes O(n+m) time, since the construction of the modular decomposition tree T(G) of the graph G can be implemented in linear time using one of the known algorithms in [8, 31]. Step 2 and the computation of the level setsL0, L1, . . . , Lh−1of the treeT(G) in Step 3 can be performed in O(n) time, since the tree T(G) contains O(n) nodes. Addition- ally, note that exactly one of the functions Draw Edgeless, Draw Complete and Draw Prime is applied on each of the nodes ofT(G).
When the functions Draw Edgeless and Draw Complete are applied on a P-node and an S-node t, respectively, the relative drawing is computed in O(|ch(t)|) time (Lemma 3.1). Lastly, function Draw Prime requiresO(ℓ·|ch(t)|2) time (Lemma 4.1), when applied on a N-nodet. Steps 4.4 and 4.5 require|ch(t)|
time and constant time respectively.
The top-down traversal of the md-treeT(G) in Step 5 is performed inO(n) time, since each nodetofT(G) is processed once. Keeping in mind thatT(G) containsO(n) nodes, the overall time complexity of Module Drawing is O(n+ m+φ(G)) whereφ(G) is the prime cost of the input graphG.
Based on the previous result and by the definition of a prime cost we ob- tain a linear-time algorithm for computing an md-drawing for certain classes of graphs. Such classes are the classes of extended P4-reducible graphs, P4- reducible graphs, cographs, along with their subclasses, such as, the trivially perfect graphs and the threshold graphs [5].
6 Implementation and Examples
We have implemented our algorithm in C++. The implementation takes as input an undirected graphGin GraphML format [4]. The vertices are thought of as rectangles with a predefined size, i.e., with a specific height and width.
Three files are produced in GraphML format: a file that contains the final drawing of G, a file that contains the md-tree T(G), and a file that contains
1AP4-reducible graph is a graph for which no vertex belongs to more than oneP4.
S S
S S
S S P
S S
S N
S P
S S
N
S P
S S S
S S
(a)
(b) (c)
Figure 6: Illustration of Module Drawing on Trans graph
all the relative drawings computed in each level of T(G). For visualization purposes, we use the yEd environment [40].
6.1 An Example of Module Drawing
In this section, we illustrate how our algorithm produces a final drawing, by showing level-by-level relative drawings, on the md-tree of the input graph. For this purpose we use an input graph from a real life application, which describes a protein interaction network (see [19] for details). More specifically, the input graph, which we will call aTrans graph, describes a network of proteins that define transcriptional regulator complexes. The md-tree of the Trans graph contains 1 P-node, 6 S-nodes, and 1 N-node. In Figure 6(a) we present the final drawing of Trans graph using Module Drawing, in Figure 6(b) we show its modular decomposition tree and in Figure 6(c) we present level-by-level relative drawings and how they are combined to result the final layout.
Starting from level 3 of the tree in Figure 6(c), we notice three S-nodes. The application of the function Draw Series results in the relative drawings as shown in the corresponding boxes. Their parent, which is a P-node, causes them to be drawn on a 1×3 grid. Finally, the root of the md-tree is an N-node; in particularG(root) is anA-shaped graph, that consists of 1 parallel module, 3 series modules, and 1 simple vertex. The final drawing reveals all modules and gives a useful insight of the structure of the Trans graph. Moreover, function
Draw Prime, which is the most expensive part of our algorithm in terms of time complexity, is applied on a graph of 5 vertices instead of 51. Notice that in the final drawing depicted in Figure 6(a) the two left most vertices are adjacent with the simple vertex but their edges are hard to follow since they cross vertices of the clique that lies next to them. However the parallel module consisting of three disjoint cliques is clearly exposed.
6.2 Drawing Examples
In all the examples we choose to draw the vertices of a graph over its edges. The height and width of all the vertices are set to 30 points. As already mentioned in the description of Module Drawing, we increase the preferred edge length ki of the i-th level, starting from the level h−1 of T(G). Thus, we setkh−1
to a constant and ki = (h−i)·kh−1, fori =h−2, h−3, . . . ,0. Obviously, ki < ki−1. We note that an alternative scheme for increasing the preferred edge length between levels is presented in [38].
For each example drawn by our algorithm, we present an additional drawing created by a spring embedder method. For this purpose we apply the Smart Organic Layout (SOL) utility of yEd [40] with desired parameters. We make clear that, there is no reason to compare our method to any spring embedder algorithm, since their drawing goals are different. We use a general purpose drawing algorithm, such as spring embedder, to obtain a reference layout of a graph. Note also that we incorporate a spring embedder method in the general framework of our approach.
(a) (b)
Figure 7: Drawings ofK9,9using (a) Module Drawing and (b) Smart Organic Layout.
In Figure 7(a) we present the drawing of a complete bipartite graph K9,9, using preferred edge lengthsk1 = 60, andk0= 120, whereas in Figure 7(b) we present the drawing of the same graph using SOL with preferred edge length set to 140. Notice, that our algorithm runs in linear time on the size of the input graph, since complete bipartite graphs are cographs [5], and manages to expose the two partitions. Due to the density of the input graph, spring embedder algorithm does not output an aesthetically pleasing result and overlaps the two partitions. However observe that in our drawing due to the exposure of the
(a) (b)
Figure 8: Drawings of a cycle of cliques using (a) Module Drawing and (b) Smart Organic Layout.
parallel modules by the grid placement there are many vertex-to-edge crossings that make non-adjacent vertices hard to identify (especially for the vertices lying in the samey-coordinate).
In Figure 8 we present a drawing of a graph known ascycle of cliques [3].
Module Drawing manages to expose all the cliques in an aesthetic pleasant way.
Also notice that Draw Prime algorithm is applied on a graph on 14 vertices (twice the number of the vertices of the basic cycle), whereas a classical spring embedder algorithm should take 56 vertices into account.
In the next two figures (Figures 9-10) we present graphs that contain only neighborhood modules. In general, the output of Module Drawing is similar to this of SOL, since both employ spring embedder algorithms. More specifically in Figure 9 (resp. Figure 10) an underlying grid (resp. path) structure is revealed.
Nevertheless, only our algorithm manages to expose the rest of the structure hidden in the graph (smaller grids, circles, paths e.t.c). This observation arises from the fact that we apply a spring embedder algorithm without the force impact of the vertices that belong to other modules.
Another interesting example can be obtained when two subgraphs are com- pletely connected to each other. More precisely, in Figure 11(a) we distinguish two cycles both on 10 vertices, where each vertex of the one cycle is adjacent to every vertex of the other. Clearly, this structure is vanished in Figure 11(b).
The last example is a graph with an md-tree of 3 levels. We present the output of our method in Figure 12(a). Notice that our method reveals three underlying structures: a gear graph2, an A-shaped graph and a complex of grids. These structures are even more obvious if one looks at the level-by-level drawings of our method. In Figure 13, we show the md-tree of the graph with
2A gear graph is a wheel graph with a vertex added between each pair of adjacent vertices of the outer cycle.
(a) (b)
Figure 9: Drawings of a graph using (a) Module Drawing and (b) Smart Organic Layout.
(a) (b)
Figure 10: Drawings of a graph using (a) Module Drawing and (b) Smart Organic Layout.
(a) (b)
Figure 11: Drawings of a graph using (a) Module Drawing and (b) Smart Organic Layout.
all the intermediate drawings computed by our method. It is useful to consider
(a) (b)
Figure 12: Drawings of a graph using (a) Module Drawing and (b) Smart Organic Layout.
Figure 13: The md-tree of the graph depicted in Figure 12.
this kind of representation as a visualization abstraction of the input graph.
7 An Alternative Approach
As we noted above in Figures 6(a) and 7(a) there are some cases in which the output drawing computed by our algorithm has many vertex-to-edge crossings so that certain adjacencies between vertices are hidden. This is because in each intermediate drawing Γ(t, G) the algorithm disregards edges outsideG(t) that will play role in a later step. For the complete and prime representative graphs it makes sense to keep them apart for the rest of the vertices since they have structural significance within the graph. However for the case of edgeless representative graphs (parallel modules) the reduction of their vertex-to-edge crossings may compromise criteria C2 and C3. Here we propose an alternative approach that tries to reduce the vertex-to-edge crossings by slightly modifying
Module Drawing.
The basic idea is to consider forthcoming edges for parallel modules caused by their grandparents inT(G). Recall that the parent of a parallel module is a P-node and, thus, its grandparent, if any, must be an S- or an N-node, since no P-node has a child another P-node inT(G). If the parent of a P-node is an S- node then instead of placing all the modules of the S-node in a circular way, we choose a parallel module with the maximum number of connected components to be drawn in another cycle outside the one corresponding to the S-node. The placement of the connected components is done in an arbitrary order. If the parent of a P-node is an N-node then the children of the P-node are considered as part of the representative graph of the N-node. Thus with the new approach the spring embedder acts on every vertex of the P-node separately, whereas with the previous algorithm those vertices are considered as a unified vertex in the prime graph.
For that purpose before computing the intermediate drawings we modify T(G) and denote the output tree by T∗(G). In the modified tree T∗(G) we have four types of internal nodes, instead of three types inT(G). Let t be an internal node ofT(G) and letch(t) ={t1, . . . , tq} be its children inT(G). We distinguish between the following two cases:
(a) If t is an S-node then let ti ∈ch(t) be the P-node having the maximum number of children inT(G) among the other P-nodes inch(t). We remove the subtree rooted atti fromT(G) and replaceti’s label by S*. The new parent of t becomes nodeti and the old parent oft now becomes parent ofti. That is, inT∗(G) the children of ti are {t} ∪ch(ti) and ti’s parent isti’s grandparent inT(G). In the resulting treeT∗(G) nodeti marks its childt.
(b) Ift is an N-node then for every P-nodeti∈ch(t) all the children ofti in T(G) become children of tinT∗(G) and nodeti is removed.
Observe that for the N-nodes we modify all of their children labelled as P-nodes, whereas for the S-nodes we consider at most one child labelled as a P-node. In Figure 14 we show the modified treeT∗(G) of the graph shown in Figure 1. Notice that node t∗2 represents node t4 in T(G) and has label S* in T∗(G). The number of children of t∗3 is increased by two with respect to that of t3, since two of t3’s children in T(G) are P-nodes. By the construction of T∗(G) it follows that the representative graphs of the S*- and N-nodes have the following properties. If t is an S*-node then G(t) is a star graph3 where the central vertex (the vertex of degree more than one) corresponds to the parent oftin T(G). Iftis an N-node thenG(t) is not necessarily a prime graph, since it contains modules coming from the P-nodes inT(G). Moreover note that an S-node inT∗(G) may have only one child.
Given the modified tree T∗(G) of a graph G, we need to reconsider Mod- ule Drawing in order to obtain the alternative drawing ofG. Observe first that
3A graph onnvertices is calledstarif it is connected andn−1 vertices have degree 1.
11 12 14 13
10
7
3 4 8 9 1 2 5 6
S
P
S* N
t∗1
t∗2 t∗3
t∗4
Figure 14: The modified treeT∗(G) of the graph depicted in Figure 1.
for P-, S-, and N-nodes we apply the same corresponding functions as in the previous case. The difference now inT∗(G) is that we have a new type of in- ternal nodetlabelled by S* so thatG(t) is a star graph. Its drawing results by placing the central vertex in the center of a cycle and the rest of the vertices are placed on the circumference. Recall that the vertices ofG(t) have non-uniform sizes. There is a straightforward way to obtain such a placement by first ap- plying Draw Complete on the vertices ofG(t) excluding the central vertex and, then, place the central vertex on the center of the cycle. Caution is required so that the central vertex does not cause any overlapping with the rest of the vertices placed on the circumference. Thus before applying Draw Complete we increase the preferred edge length by a proportional function of the diagonal length of the central box. By that way we guarantee that no vertex overlapping occurs in the relative drawing ofG(t). It is interesting to note that the main difference with the previous version is that we introduce a new type of label in the modified tree that requires the proper description of the corresponding relative drawing technique.
Regarding the running time observe that modifying the treeT(G) takesO(n) time since both trees T(G) and T∗(G) contain O(n) nodes. The function for drawing star graphs for the S*-nodes requires the same amount of time needed for applying Draw Complete. However the vertex set of a representative graph of an N-node in T∗(G) may be larger than the corresponding one in T(G), implying an additional cost to the overall running time.
A drawing of the Trans graph computed by the second approach is shown in Figure 15 (a). Notice that the spring embedder is able to distinguish the vertices of the parallel module shown in Figure 6 in such a way that the adjacencies between those vertices and the simple vertex are easy to follow. In Figure 15 (b)
(a) (b)
Figure 15: Two drawings computed by the second approach. (a) and (b) contain the graphs shown in Figures 6 and 7, respectively.
we present the drawing computed by the alternative algorithm for the complete bipartite graph shown in Figure 7. Observe that although the vertex-to-edge crossings are not minimized in the output drawing, there are no such crossings between the vertices of the parallel module placed in the outer cycle.
8 Concluding Remarks
In this paper we have presented a divide-and-conquer technique for drawing undirected graphs, based on their modular decomposition tree, where each dis- joint induced subgraph (module) is drawn according to its corresponding struc- ture (edgeless, complete or prime). For certain classes of graphs, the structure of their modular decomposition trees ensures that each tree node can be pro- cessed in linear time. It turns out that our algorithm also reveals the structure of a graph and exposes regular structures of its subgraphs. Thus, modular de- composition can be thought as a quite effective clustering technique that can be exploited to give a better insight in many graphs. By grouping vertices with the same neighborhood a great reduction on the size of the graph can be achieved, without loosing any information for the connectivity among modules.
It is interesting to design efficient drawing algorithms for certain classes of prime graphs, by exploiting their structural properties. In this way the applica- tion of the spring embedder, which is the most expensive part of our algorithm, will be avoided. Also, further research includes an investigation for the edge crossings which appear between modules. It would be interesting to know if the adjacency between two modules of vertices can be drawn in a planar way by applying confluent drawings introduced in [10]. Finally, another interesting point is to apply other linear-time hierarchical decomposition algorithms, such as split decomposition which divides a connected graph into stars, cliques and prime graphs [7].
Acknowledgements
The authors would like to express their thanks to the anonymous referees whose suggestions helped improve the presentation of the paper.
References
[1] H. Bodlaender and U. Rotics. Computing the treewidth and the minimum fill-in with the modular decomposition. Algorithmica, 36:375–408, 2003.
[2] F. Brandenburg. Designing graph drawings by layout graph grammars. In Proc. 2nd Int. Symp. Graph Drawing (GD’94), volume 894 ofLecture Notes in Computer Science, pages 416–427, 1994.
[3] F. Brandenburg. Graph clustering 1: circles of cliques. In Proc. 5th Int.
Symp. Graph Drawing (GD’97), volume 1353 ofLecture Notes in Computer Science, pages 158–168, 1997.
[4] U. Brandes, M. Eiglsperger, I. Herman, M. Himsolt, and M. Marshall.
Graphml progress report: structural layer proposal. InProc. 9th Int. Symp.
Graph Drawing (GD’01), volume 2265 of Lecture Notes in Computer Sci- ence, pages 501–512, 2001.
[5] A. Brandst¨adt, V. Le, and J. Spinrad. Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, 1999.
[6] B. Courcelle, J. Makowsky, and U. Rotics. Linear time solvable optimiza- tion problems on graphs of bounded clique-width. Theory Comput. Syst., 33:125–150, 2000.
[7] E. Dahlhaus. Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition.J. Algorithms, 36:205–
240, 2000.
[8] E. Dahlhaus, J. Gustedt, and R. McConnell. Efficient and practical algo- rithms for sequential modular decomposition. J. Algorithms, 41:360–387, 2001.
[9] G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Algorithms for the Visualization of Graphs. Prentice-Hall, 1999.
[10] M. Dickerson, D. Eppstein, M. Goodrich, and J. Meng. Confluent draw- ings: visualizing non-planar diagrams in a planar way. In Proc. 11th Int.
Symp. Graph Drawing (GD’03), volume 2912 ofLecture Notes in Computer Science, pages 1–12, 2004.
[11] P. Eades and Q. Feng. Drawing clustered graphs on an orthogonal grid.
In Proc. 5th Int. Symp. Graph Drawing (GD’97), volume 1353 ofLecture Notes in Computer Science, pages 146–157, 1997.
[12] P. Eades, Q. Feng, and X. Lin. Straight-line drawing algorithms for hierar- chical graphs and clustered graphs. InProc. 4th Int. Symp. Graph Drawing (GD’96), volume 1190 of Lecture Notes in Computer Science, pages 113–
128, 1996.
