Bachlbrandenburggmach2004.8.2.dvi

Journal of Graph Algorithms and Applicationshttp://jgaa.info/ vol. 8, no. 2, pp. 215–238 (2004) Computing and Drawing Isomorphic Subgraphs
Batavis GmbH & Co. KG, 94036 Passau, Germany University of Passau, 94030 Passau, Germany ur Informatik III, TU M¨ unchen, 85746 Garching, Germany The isomorphic subgraph problem is finding two disjoint subgraphs of a graph which coincide on at least k edges. The graph is partitionedinto a subgraph, its copy, and a remainder. The problem resembles theNP-hard largest common subgraph problem, which searches copies of agraph in a pair of graphs. In this paper we show that the isomorphic sub-graph problem is NP-hard, even for restricted instances such as connectedouterplanar graphs. Then we present two different heuristics for the com-putation of maximal connected isomorphic subgraphs. Both heuristics useweighting functions and have been tested on four independent test suites.
Finally, we introduce a spring algorithm which preserves isomorphic sub-graphs and displays them as copies of each other. The drawing algorithmyields nice drawings and emphasizes the isomorphic subgraphs.
The work by F.-J. Brandenburg was supported in part by the German Science Foun-dation (DFG), grant Br 835/9-1. Corresponding author: F.-J. Brandenburg.
S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) Graph drawing is concerned with the problem of displaying graphs nicely. Thereis a wide spectrum of approaches and algorithms [10]. Nice drawings help inunderstanding the structural relation modeled by the graph. Bad drawings aremisleading. This has been evaluated by HCI experiments [31, 32], which haveshown that symmetry is an important factor in the understanding of graphdrawings and the underlying relational structure. There is an information the-oretic foundation and explanation for this observation: symmetry increases theredundancy of the drawing and saves bits for the information theoretic repre-sentation of a graph. Drawings of graphs in textbooks [33] and also the winningentries of the annual Graph Drawing Competitions and the logos of the sym-posia on Graph Drawing are often symmetric. In [3] symmetry is used for nicedrawings without defining nice.
Another application area for isomorphic subgraphs comes from theoretical biology. It is of great interest to compare proteins, which are complex structuresconsisting of several 10000 of atoms. Proteins are considered at different ab-straction levels. This helps reducing the computational complexity and detect-ing hidden structural similarities, which are represented as repetitive structuralsubunits. Proteins can be modeled as undirected labeled graphs, and a pairof repetitive structural subunits corresponds to a subgraph and its isomorphiccopy.
Symmetry has two directions: geometric and graph theoretic. A graph theo- retic symmetry means a non-trivial graph automorphism. The graph automor-phism problem has been investigated in depth by Lubiw [27]. She proved theNP-hardness of many versions. However, the general graph automorphism andgraph isomorphism problems are famous open problems between polynomialtime and NP-hardness [19, 27]. A graph has a geometric symmetry if it hasa drawing with a rotational or a reflectional invariant. Geometric symmetriesof graphs correspond to special automorphisms, which has been elaborated in[14]. Geometric symmetries have first been studied by Manning [28, 29], whohas shown that the detection of such symmetries is NP-hard for general graphs.
However, for planar graphs there are polynomial time solutions [23, 22, 24, 29].
Furthermore, there is a relaxed approach by Chen et al. [8] which reduces agiven graph to a subgraph with a geometric symmetry by node and edge dele-tions and by edge contractions. Again this leads to NP-hard problems.
Most graphs from applications have only a trivial automorphism. And small changes at a graph may destroy an automorphism and the isomorphism of apair of graphs. Thus graph isomorphism and graph automorphism are veryrestrictive. More flexibility is needed, relaxing and generalizing the notions ofgeometric symmetry and graph automorphism. This goal is achieved by therestriction to subgraphs. Our approach is the notion of isomorphic subgraphs,which has been introduced in [5] and has first been investigated in [1, 2]. Theisomorphic subgraph problem is finding two large disjoint subgraphs of a givengraph, such that one subgraph is a copy of the other. Thus a graph G partitionsinto G = H1 + H2 + R, where H1 and H2 are isomorphic subgraphs and R is the S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) remainder. From another viewpoint one may create graphs using the cut©operation of a graph editor in the following way: select a portion of a graph,create a new copy thereof, and connect the copy to the original graph.
The generalization from graph automorphism to isomorphic subgraphs is related to the generalization from graph isomorphism to largest common sub-graph. The difference lies in the number of input graphs. The coincidence orsimilarity of the subgraphs is measured in the number of edges of the com-mon subgraphs, which must be 100% for the automorphism and isomorphismproblems, and which may be less for the more flexible generalizations.
The isomorphic subgraph problem and the largest common subgraph prob- lem are NP-hard, even when restricted to connected outerplanar graphs and to2-connected planar graphs [1, 2, 19]. For 3-connected planar graphs the largestcommon subgraph problem remains NP-hard as a generalization of Hamiltoniancircuit, whereas the complexity of the isomorphic subgraph problem is open inthis case. Both problems are tractable, if the graphs have tree-width k and thegraphs and the isomorphic subgraphs are k-connected [6], where k is some con-stant. In particular, isomorphic subtrees [1, 2] and the largest common subtreeof two rooted trees can be computed in linear time. For arbitrary graphs theisomorphic subgraph problem seems harder than the largest common subgraphproblem. An instance of the largest common subgraph problem consists of a pairof graphs. The objective is a matching between pairs of nodes inducing an iso-morphism, such that the matched subgraphs are maximal. For the isomorphicsubgraph problem there is a single graph. Now the task is finding a partitioninto three components, H1, H2, and a remainder R, and an isomorphism pre-serving matching between the subgraphs H1 and H2. This is a hard problem,since both graph partition and graph isomorphism are NP-hard problems.
We approach the computation of maximal connected isomorphic subgraphs in two ways: First, the matching approach uses different weighting parametersfor a local bipartite matching that determines the local extension of a pair ofisomorphic subgraphs by pairs of nodes from the neighborhood of two isomor-phic nodes. The computation is repeated with different seeds. This approachcaptures both the partition and the isomorphism problems. Our experimentsare directed towards the appropriateness of the approach and the effectivenessof the chosen parameters. The measurements are based on more than 100.000computations conducted by Bachl for her dissertation [2]. Second, the squaregraph approach uses Levi's transformation [26] of common adjacencies into acomparability graph. We transform a graph into its square graph, which is thensearched for large edge weighted cliques by a heuristic. Both approaches areevaluated and compared on four test suites. These tests reveal versions withbest weighting functions for each of the two approaches. To stabilize the resultsboth algorithms must be applied repeatedly with different seeds. However, thecomputed common subgraphs are sparse, and are often trees with just a fewadditional edges. Between the two approaches there is no clear winner by ourmeasurements. Concerning the size of the computed connected isomorphic sub-graphs the matching outperforms the product graph method on sparse graphsand conversely on dense graphs. A major advantage of the matching approach S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) over the product graph approach is that it operates directly on the given graph.
The product graph approach operates on square graphs, whose size is quadraticin the size of the input graphs.
As an application in graph drawing we present a spring algorithm which preserves isomorphic subgraphs and displays them as copies of each other. Thealgorithm is an extension of the Fruchterman and Reingold approach [18]. Eachnode and its copy are treated identically by averaging forces and moves. Anadditional force is used to separate the two copies of the subgraphs. With aproper setting of the parameters of the forces this gives rather pleasing pictures,which cannot be obtained by standard spring algorithms.
The paper is organized as follows: First we define the isomorphic subgraph problem. In Section 3 we show its NP-hardness, even for very restrictive cases,and address the problem of computing large isomorphic subgraphs. In Section 4we introduce two different algorithms which have been evaluated and comparedin several versions and on different test suites. Finally, in Section 5 we presenta graph drawing algorithm for isomorphic subgraphs.
We consider undirected graphs G = (V, E) with a set of nodes V and a setof edges E. Edges are denoted by pairs e = (u, v). For convenience, self-loops and multiple edges are excluded. The set of neighbors of a node v is N(v) = {u ∈ V (u, v) ∈ E}. Observe that a node is not its own neighbor. If vis a node from a distinguished subgraph H, then the new neighbors of v are itsneighbors not in H.
In many applications there are node and edge labels and the labels have to be respected by an isomorphism. This is discarded here, although the labels are agreat help in the selection and association of nodes and edges for the isomorphicsubgraph problem. Often additional information is used for an initial seed beforestarting the comparison of two graphs. A good seed is an important factor, asour results shall confirm.
Definition 1 Let G = (V, E) be a graph and let V
⊆ V and E

⊆ E be subsets
of nodes and edges. The node-induced subgraph G[V
] = (V
, E
) consists of
the nodes of V
and the edges E
= E ∩ V
× V
. The edge-induced subgraph
G[E

] = (V

, E

) consists of the edges of E

and their incident nodes V

= {u, v ∈ V (u, v) ∈ E

}. An isomorphism between two graphs is a bijection φ : G → G
on the sets of nodes that preserves adjacency. If G = G
, φ is a graph automorphism, which isa permutation of the set of nodes that preserves adjacency. If v
= φ(v), then vand v
are called a pair of isomorphic copies, and similarly for a pair of edges.
A common subgraph of two graphs G and G
is a graph H that is isomorphic to G[E] and G
[E
] for some subsets of the sets of edges of G and G
. Moreprecisely, H is an edge-induced common subgraph of size k, where k is the number S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) of edges of H. Accordingly, H is a node-induced common subgraph if G[E] and G
[E
] are node-induced subgraphs.
Our notions of isomorphic subgraphs use only single graphs.
Definition 2
The isomorphic node-induced subgraph problem, INS:
Instance: A graph G = (V, E) and an integer k.
Question: Does G contain two disjoint node-induced common subgraphs H1 and
H2 with at least k edges? Definition 3
The isomorphic edge-induced subgraph problem, IES:
Instance: A graph G = (V, E) and an integer k.
Question: Does G contain two disjoint edge-induced common subgraphs H1 and
H2 with at least k edges? For INS and IES the graph G partitions into two isomorphic subgraphs H1 and H2 and a remainder R such that G = H1 + H2 + R. When computing iso-morphic subgraphs the subgraphs H1 and H2 are supposed to be connected andmaximal. IES is our most flexible version, whereas INS seems more appropriatefor graph drawings. Notice that also in the node-induced case the size of thecommon subgraphs must be measured in terms of the common edges. Other-wise, the problem may become meaningless. As an example consider an n × mgrid graph with n, m even. If V1 consists of all even nodes in the odd rows andof all odd nodes in the even rows, and V2 = V V1, then V1 and V2 have maximalsize. However, their induced subgraphs are discrete with the empty set of edges.
Common subgraphs can be represented as cliques in so-called comparability or product graphs. This has been proposed by Levi [26] for the computationof maximal common induced subgraphs of a pair of graphs. Then a commonsubgraph one-to-one corresponds to a clique in the comparability graph. Weadapt this concept to isomorphic subgraphs of a single graph.
Definition 4 The square of a graph G = (V, E) is an undirected graph G2 =
(V 2, E2), whose nodes are the pairs of distinct nodes of G with V 2 = {(u, v) u =
v and u, v ∈ V }. The edges of G2 are generating or stabilizing edges betweenpairwise distinct nodes u1, v1, u2, v2. ((u1, u2), (v1, v2)) is a generating edge, ifboth (u1, v1) and (u2, v2) are edges of E. ((u1, u2), (v1, v2)) is a stabilizing edge,if there are no such edges in E. There is no edge in G2, if there is exactly oneedge between the respective nodes in G. Each pair of edges in G with pairwise distinct endnodes induces four gen- erating edges in G2, and accordingly there are four stabilizing edges resultingfrom two pairs of non-adjacent nodes. Hence, square graphs are dense and havean axial symmetry. In the later clique searching algorithm generating edges willreceive a high weight of size V 2, and stabilizing edges are assigned the weightone.
S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) Lemma 1 The square graph of an undirected graph has an axial symmetry.
Proof: Let G = (V, E) and G2 be the graph and its square. Use the Y -axis for
the axial symmetry of G2. For each pair of nodes u, v ∈ V with u = v there is a
pair of symmetric nodes of G2 such that (u, v) is placed at (−x, y) and (v, u) is
placed at (+x, y) for some x, y, such that distinct nodes are placed at distinct
positions. If v1, v2, v3, v4 are distinct nodes of V , then the edges induced by these
nodes in G2 are symmetric, mapping ((v1, v2), (v3, v4)) to ((v2, v1), (v4, v3)). 2
The usability of square graphs for the computation of isomorphic subgraphs is based on the following fact.
Theorem 1 Let V1 and V2 be subsets of the set of nodes V of a graph G.
H1 = G[V1] and H2 = G[V2] are isomorphic disjoint node-induced subgraphs withan isomorphism φ : V1 → V2 if and only if the set of nodes {(v, φ(v)) v ∈ V1}induces a clique in the square graph G2. The isomorphism φ can be retrievedfrom the clique. Proof: If φ is an isomorphism from H1 into H2, then for nodes u, v ∈ V1 with
u = v the nodes (u, φ(u)) and (v, φ(v)) are connected in G2 by a generating edgeor by a stabilizing edge. Hence, the set of nodes {(v, φ(v)) v ∈ V1} induces aclique in G2. Conversely, suppose that a set of nodes W of G2 defines a clique.
Let V1 = {v1 (v1, v2) ∈ W } and V2 = {v2 (v1, v2) ∈ W } be the projectionsonto the first and second components. If (u1, u2) and (v1, v2) are nodes of W ,then the nodes u1, v1, u2, v2 are pairwise distinct. Hence V1 ∩ V2 = ∅. Define φ : V1 → V2 by φ(v1) = v2 if (v1, v2) ∈ W . From the distinctness φ is a bijection.
Moreover, for nodes u1, v1 ∈ V1 and their images u2, v2 ∈ V2 either there aretwo edges (u1, v1) and (u2, v2) in G or these pairs of nodes are not adjacent.
Hence, G[V1] and G[V2] are isomorphic disjoint node-induced subgraphs.
Consequently, a maximal clique in the node square graph G2 corresponds to a pair of maximal node-induced subgraphs in G. However, the isomorphicsubgraphs of G are not necessarily connected. Connectivity can be establishedby the requirement that the clique nodes in G2 are connected by generatingedges.
Accordingly, we use so-called edge-square graphs for the edge-induced iso- morphic subgraph problem.
Definition 5 The edge-square graph of a graph G = (V, E) consists of the pairs
of edges of G with distinct endnodes {(e, e
) e, e
∈ E and u, v, u
, v
are pairwise
distinct for e = (u, v) and e
= (u
, v
)} as its nodes. Two such nodes (e, e
) and
(f, f
) are connected by an undirected edge if and only if the endnodes of e, e

and of f, f
are pairwise distinct and either e, e
and f, f
are adjacent in G or
e, e
and f, f
are not adjacent in G. In the first case, the edge between (e, e
)and (f, f
) is a generating edge, in the latter case a stabilizing edge. Notice that the edge-square graph of G = (V, E) is the node square graph of its edge graph Ge = (E, F ) with (e, e
) ∈ F if and only if the edges e and e
are adjacent in G. Its size is quadratic in the number of edges of G.
S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) Isomorphic Subgraph Problems
The largest common subgraph problem [19] generalizes many other NP-hardgraph problems such as the clique, Hamiltonian circuit, and subgraph isomor-phism problems. The isomorphic subgraph problem is similar; however, it usesonly a single graph. The analogy between the largest common subgraph prob-lem and the isomorphic subgraph problem is not universal, since graph isomor-phism is a special case of the largest common subgraph problem, whereas graphautomorphism is not a special case of the isomorphic subgraph problem. Nev-ertheless, the isomorphic subgraph problems are NP-hard, too, even for relatedspecializations. However, at present we have no direct reductions between theisomorphic subgraph and the largest common subgraph problems.
When restricted to trees the isomorphic subtree problem is solvable in linear time. This has been established in [1, 2] for free and rooted, ordered and un-ordered trees by a transformation of trees into strings of pairs of parentheses anda reduction of the largest common subtree problem to a longest non-overlappingwell-nested substring and subsequence problems. However, the isomorphic sub-tree problem requires trees as common subgraphs of a tree. This is not therestriction of the isomorphic subgraph problem to a tree, where the isomor-phic subgraphs may be disconnected. In [8] there are quite similar results for arelated problem.
Theorem 2 The isomorphic subgraph problems INS and IES are NP-hard.
These problems remain NP-hard if the graph G is
• 1-connected outerplanar and the subgraphs are or are not connected. • 2-connected planar and the subgraphs are 2-connected. Proof: We reduce from the strongly NP-hard 3-partition problem [19]. First
consider IES.
Let A = {a1, . . , a3m} and B ∈ N be an instance of 3-partition with a size s(a) for each a ∈ A and B/4 < s(a) < B/2. The elements of A must be groupedinto m triples whose sizes sum up to B.
We construct a graph G as shown in Figure 1. The left subgraph L consists of 3m fans, where the i-th fan is a chain of s(ai) nodes which are all connected to v1. It is called the s(ai)-fan. The right subgraph R has m fans each consistingof a chain of B nodes which are all connected to v2. The fans of R are called B-fans. Let k = 2Bm − 3m. Then G has 2k + 2m + 1 edges.
Now G has an IES solution of size k if and only if there is a solution of First, let A1, . . , Am be a solution of 3-partition with each Ai containing three elements of A. Define H1 = L and H2 = R and a bijection φ : H1 → H2,such that v1 is mapped to v2 and for each a ∈ Aj (1 ≤ j ≤ m) the s(a)-fans aremapped to the j-th B-fan. This cuts two edges of each B-fan. Then H1 and H2 (2s(a) − 1) = 2Bm − 3m = k common edges and IES has a solution.
Conversely, let H1 and H2 be a solution of IES with k = 2Bm − 3m. Then one of the graphs must be L and the other is R, and they must be mapped S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) Figure 1: Reduction to IES for connected outerplanar graphs to each other by φ, such that only 2m + 1 edges go lost by the mapping. Inparticular, φ(v1) = v2, since the degree of v1 and v2 is Bm + 1, whereas allother nodes have a degree of at most three. Hence, if φ(v1) = v2, then at least2 · (Bm + 1 − 3) edges go lost and at most E − 2(Bm − 2) edges are left for H1and H2. Since E = 4Bm − 4m + 1 and B > 1, less than k − 3 edges are leftfor each of H1 and H2, contradicting the assumption φ(v1) = v2. Let v1 be in H1 and v2 in H2. If the subgraphs must be connected, then H1 is a subgraphof L and H1 = L to achieve the bound k, and similarly H2 is a subgraph of R.
This is also true, if H1 and H2 may be disconnected. To see this suppose thecontrary. If j > 0 edges of R are in H1, then at least j + 1 nodes of R are in H1. Each such node decreases the number of edges for the isomorphic copies atleast by one, since the edges to v2 go lost. And for every three s(ai)-fans from L at least two edges from R go lost. Since R has k + 2m edges, j = 0, H1 = Land H2 is a subgraph of R with k edges. Now every s(ai)-fan must be mappedto a B-fan, such that all edges of the s(ai)-fan are kept. Since B4 < s(a) < B2 , exactly three s(ai)-fans must be mapped to one B-fan, and each B-fan loosesexactly two edges. Hence, there is a solution of 3-partition.
The reduction from 3-partition to INS is similar. Consider the graph G from Figure 2 and let k = 3Bm − 6m.
The left subgraph L consists of 3m fans, where the i-th fan is a chain of s(ai) + (s(ai) − 1) nodes and the nodes at odd positions are connected to v1.
The right subgraph R has m fans where each fan has exactly B + (B − 1) nodesand the nodes at odd positions are connected to v2. The nodes v1 and v2 areadjacent.
By the same reasoning as above it can be shown that G has two isomorphic S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) Figure 2: Reduction to INS for connected outerplanar graphs node-induced subgraphs H1 and H2, with k edges each, and which may beconnected or not if and only if H1 = L if and only if there is a solution of3-partition.
Accordingly, we can proceed if we increase the connectivity and consider 2-connected planar graphs. For IES consider the graph G from Figure 3 andlet k = 3Bm − 3m. Again it can be shown that L and R are the edge-inducedisomorphic subgraphs. The construction of the graph for INS is left to thereader. However, the isomorphic subgraph problem is polynomially solvable for2-connected outerplanar graphs [6].
Computing Isomorphic Subgraphs
In this section we introduce two different heuristics for the computation of max-imal connected isomorphic subgraphs. The isomorphic subgraph problem isdifferent from the isomorphism, subgraph isomorphism and largest commonsubgraph problems. There is only a single graph, and it is a major task tolocate and separate the two isomorphic subgraphs. Moreover, graph propertiessuch as the degree and adjacencies of isomorphic nodes are not necessarily pre-served, since an edge from a node in one of the isomorphic subgraphs may endin the remainder or in the other subgraph. The size of the largest isomorphicsubgraphs can be regarded as a measure for the self-similarity of a graph in thesame way as the size of the largest common subgraph is regarded as a measurefor the similarity of two graphs.
S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) Figure 3: Reduction to IES for 2-connected planar graphs The Matching Approach
Our first approach is a greedy algorithm, whose core is a bipartite matching forthe local search. The generic algorithm has two main features: the initializationand a weighting function for the nodes. Several versions have been tested in [2].
The algorithm proceeds step by step and attempts to enlarge the intermediatepair of isomorphic subgraphs by a pair of new nodes, which are taken fromthe neighbors of a pair of isomorphic nodes. The correspondence between theneighbors is computed by a weighted bipartite matching. Let G = (V, E) be thegiven graph, and suppose that the subgraphs H1 and H2 have been computedas copies of each other. For each pair of new nodes (v1, v2) not in H1 and H2the following graph parameters are taken into account: • w1 = degree(v1)+degree(v2) • w2 = − degree(v1)−degree(v2) • w3 = −(the number of common neighbors) • w4 = the number of new neighbors of v1 and v2 which are not in H1 ∪ H2 • w5 = the graph theoretical distance between v1 and v2 • w6 = the number of new isomorphic edges in (H1 ∪ v1, H2 ∪ v2).
These parameters can be combined arbitrarily to a weight W = λiwi with 0 ≤ λi ≤ 1. Observe that w2 and w3 are taken negative. Let w0 = The greedy algorithm proceeds as follows: Suppose that H1 and H2 are disjoint connected isomorphic subgraphs which have been computed so far andare identified by the mapping φ : V1 → V2 on their sets of nodes. The algorithmselects the next pair of nodes (u1, u2) ∈ V1 × V2 with u2 = φ(u1) from thequeue of such pairs. It constructs a bipartite graph whose nodes are the new S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) neighbors of u1 and u2. For each such pair (v1, v2) of neighbors of (u1, u2) with v1, v2 ∈ V1 ∪ V2 and v1 = v2 there is an edge with weight W (v1, v2) = wi, where wi is any of the above weighting functions. For example, W (v1, v2) is the sumof the degrees of v1 and v2 for w1. There is no edge if v1 = v2. Then computean optimal weighted bipartite matching. For the matching we have used theKuhn-Munkres algorithm (Hungarian method) [9] with a runtime of O(n2m).
In decreasing order by the weight of the matching edges the pairs of matchednodes (v1, v2) are taken for an extension of H1 and H2, provided that (v1, v2)passes the isomorphism test and neither of them has been matched in precedingsteps. The isomorphism test is only local, since each time only one new nodeis added to each subgraph. Since the added nodes are from the neighborhood,the isomorphic subgraphs are connected, and they are disjoint since each nodeis taken at most once.
In the node-induced case, a matched pair of neighbors (v1, v2) is added to the pair of isomorphic subgraphs if the isomorphism can be extended by v1 and v2.
Otherwise v1 and v2 are skipped and the algorithm proceeds with the endnodesof the next matched edge. In the case of edge-induced isomorphic subgraphs thealgorithm successively adds pairs of matched nodes and all edges between pairsof isomorphic nodes. Each node can be taken at most once, which is checked ifu1 and u2 have common neighbors.
For each pair of starting nodes the algorithm runs in linear time except for the Kuhn-Munkres algorithm, which is used as a subroutine on bipartitegraphs, whose nodes are the neighbors of two nodes. The overall runtime of ouralgorithm is O(n3m). However, it performs much better in practice, since theexpensive Kuhn-Munkres algorithm often operates on small sets. The greedyalgorithm terminates if there are no further pairs of nodes which can extend thecomputed isomorphic subgraphs, which therefore are maximal.
For an illustration consider the graph in Figure 4 with (1, 1
) as the initial pair of isomorphic nodes. The complete bipartite graph from the neighbors hasthe nodes 2, 3, 4 and 6, 7. Consider the sum of degrees as weighting function.
Then w1(3, 6) + w1(2, 7) = 15 is a weight maximal matching; the edges (2, 6)and (3, 7) have the same weight. First, node 3 is added to 1 and 6 is added to1
. In the node-induced case, the pair (2, 7) fails the isomorphism test and isdiscarded. In the next step, the new neighbors of the pair (3, 6) are considered,which are 2, 4, 5 and 2, 5. In the matching graph there is no edge between thetwo occurrences of 2 and 5. A weight maximal matching is (2, 5) and (4, 2)with weight 14. Again the isomorphism test fails, first for (2, 5) and then for(4, 2). If it had succeeded with (2, 5) the nodes 2 and 5 were blocked and theedge (4, 2) were discarded. Hence, the approach finds only a pair of isomorphicsubgraphs whereas the optimal solution for IN S are the subgraphs induced by {1, 3, 4, 7} and by {2, 5, 6, 1
} which are computed from the seed (7, 1
). In theedge-induced case there are the copies (3, 6) and (2, 7) from the neighbors of(1, 1
) discarding the edge (2, 3) of G. Finally, (4, 5) is taken as neighbors of(3, 6). The edges of the edge-induced isomorphic subgraphs are drawn bold.
Figure 5 shows the algorithm for the computation of node-induced sub- graphs. P consists of the pairs of nodes which have already been identified by S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) Figure 4: The matching approach initialize(P );while (P = ∅) do (u1, u2) = next(P); delete (u1, u2) from P ; N1 = new neighbors of u1; N2 = new neighbors of u2; M = optimal weighted bipartite matching over N1 and N2;forall edges(v1, v2) of M decreasingly by their weight do if G[V1 ∪ {v1}] is isomorphic to G[V2 ∪ {v2}] then P = P ∪ {(v1, v2)}; V1 = V1 ∪ {v1}; V2 = V2 ∪ {v2}; Figure 5: The matching approach for isomorphic node-induced subgraphs.
the isomorphism.
In our experiments a single parameter wi or the sum w0 is taken as a weight of a node. The unnormalized sum worked out because the parameters hadsimilar values.
The initialization of the algorithm is a critical point. What is the best pair of distinct nodes as a seed? We ran our experiments • repeatedly for all O(n2) pairs of distinct nodes • with the best pair of distinct nodes according to the weighting function • repeatedly for all pairs of distinct nodes, whose weight is at least 90% of the weight of the best pair.
If the algorithm runs repeatedly it keeps the largest subgraphs. Clearly, the all pairs version has a O(n2) higher running time than the single pair version.
The 90% best weighted pairs is a good compromise between the elapsed timeand the size of the computed subgraphs.
The Square Graph Approach
In 1972 Levi [26] has proposed a transformation of the node-induced commonsubgraph problem of two graphs into the clique problem of the so-called node- S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) product or comparability graph. For two graphs the product graph consists of allpairs of nodes from the two graphs and the edges represent common adjacencies.
Accordingly, the edge-induced common subgraph problem is transformed intothe clique problem of the edge-product graph with the pairs of edges of thetwo graphs as nodes. Then a maximal clique problem must be solved. Thiscan be done by the Bron-Kerbosch algorithm [7] or approximately by a greedyheuristic [4]. The Bron-Kerbosch algorithm works recursively and is widelyused as an enumeration algorithm for maximal cliques. However, the runtimeis exponential, and becomes impractical for large graphs. A recent study byKoch [25] introduces several variants and adaptations for the computation ofmaximal cliques in comparability graphs representing connected edge-inducedsubgraphs.
We adapt Levi's transformation to the isomorphic subgraph problem. In the node-induced case, the graph G is transformed into the (node) square graph,whose nodes are pairs of nodes of G. In the edge-induced case, the edge-squaregraph consists of all pairs of edges with distinct endnodes. The edges of thesquare graphs express a common adjacency. They are classified and labeled asgenerating and as stabilizing edges, representing the existence or the absence ofcommon adjacencies, and are assigned high and low weights, respectively.
Due to the high runtime of the Bron-Kerbosch algorithm we have developed a local search heuristic for a faster computation of large cliques. Again we useweighting functions and several runs with different seeds. Several versions oflocal search strategies have been tested in [20]. The best results concerningquality and speed were achieved by the algorithm from Figure 6, using thefollowing weights. The algorithm computes a clique C and selects a new node u with maximal weight from the set of neighbors U of the nodes in C. Eachedge e of the square graph G2 is a generating edge with weight w(e) = V 2 or astabilizing edge of weight w(e) = 1. For a set of nodes X define the weight of a node v by wX(v) = x∈X w(v, x). The weight of a set of nodes is the sum of the weights of its elements. In the post-processing phase the algorithm exchanges anode in the clique with neighboring nodes, and tests for an improvement.
Construct the square graph G2 = (X, E) of G;Select two adjacent nodes v1 and v2 such that wX({v1, v2}) is maximal; C = {v1, v2}; U = N(v1) ∩ N(v2); while U = ∅ do select u ∈ U such that wC(u) + wC∪U (u) is maximal; U = U ∩ N(u); forall nodes v ∈ C do forall nodes u ∈ C do if C − {v} ∪ {u} is a cliquethen C = C − {v} ∪ {u}; Figure 6: The square graph approach.
In our experiments the algorithm is run five times with different pairs of S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) nodes in the initialization, and it keeps the clique with maximal weight foundso far. The repetitions stabilize the outcome of the heuristic. The algorithmruns in linear time in the size of G2 provided that the weight of each node canbe determined in O(1) time.
The experiments were performed on four independent test suites [30].
• 2215 random graphs with a maximum of 10 nodes and 14 edges • 243 graphs generated by hand • 1464 graphs selected from the Roma graph library [35], and • 740 dense graphs.
These graphs where chosen by the following reasoning. For each graph from the first test suite the optimal result has been computed by an exhaustive searchalgorithm.
The graphs from the second test suite were constructed by taking a single graph from the Roma library, making a copy and adding a few nodes and edgesat random. The threshold is the size of the original graph. It is a good boundfor the size of the edge-induced isomorphic subgraphs. The goal is to detectand reconstruct the original graph. For INS, the threshold is a weaker estimatebecause the few added edges may destroy node-induced subgraph isomorphism.
Next all connected graphs from the Roma graph library with 10, 15, . . , 60 nodes are selected and inspected for isomorphic subgraphs. These graphs havebeen used at several places for experiments with graph drawing algorithms.
However, these 1464 graphs are sparse with E ∼ 1.3 V . This specialty hasnot been stated at other places and results in very sparse isomorphic subgraphs.
It is reflected by the numbers of nodes and edges in the isomorphic subgraphsas Figure 8 displays.
Finally, we randomly generated 740 dense graphs with 10, 15, . . , 50 nodes and 25, 50, . . , 0.4 · n2 edges, with five graphs for each number of nodes andedges, see Table 1.
number of graphs
Table 1: The dense graphs S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) First, consider the performance of the matching approach. It performs quite well, particularly on sparse graphs. The experiments on the first three testsuites give a uniform picture. It finds the optimal subgraphs in the first testsuite. In the second test suite the original graphs and their copies are detectedalmost completely when starting from the 90% best weighted pairs of nodes, seeFigure 7.
difference of degree (w2) common neighbours (w3) new neighbours (w4) isomorphic edges (w6) number of nodes in every subgraph number of nodes in the graph Figure 7: The matching approach computing isomorphic edge-induced sub-graphs of the second test suite for the 90% best weighted pairs of startingnodes.
The weights w2, w3 and w6 produce the best results. The total running time is in proportion to the number of pairs of starting nodes. For the 90% bestweighted pairs of nodes it is less than two seconds for the largest graphs with100 nodes and the weights w0, w1, w4 and w5 on a 750 MHz PC with 256 MBRAM, 30 seconds for w2 and 100 seconds for w3 and w6, since in the latter casesthe algorithm iterates over almost all pairs of starting nodes. In summary, thedifference of degree weight w2 gives the best performance.
For the third test suite the matching heuristic detects large isomorphic sub- graphs. Almost all nodes are contained in one of the node- or edge-inducedisomorphic subgraphs, which are almost trees. This can be seen from the smallgap between the curves for the nodes and edges in Figure 8. There are only oneor two more edges than nodes in each subgraph. This is due to the sparsity ofthe test graphs and shows that the Roma graphs are special. Again weight w2performs best, as has been discovered by tests in [2].
S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) edges in the matching approach nodes in the matching approach edges in the square graph approach nodes in the square graph approach number of nodes and edges in every subgraph number of nodes in the graph Figure 8: Comparison of the approaches on the Roma graphs matching approach square graph approach number of nodes in the graph Figure 9: Run time of the approaches on the Roma graphs S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) Finally, on the dense graphs the matching heuristic with the 90% best weighted pairs of starting nodes and weight w2 finds isomorphic edge-inducedsubgraphs which together contain almost all nodes and more than 1/3 of theedges. In the node-induced case each subgraph contains about 1/4 of the nodesand decreases from 1/5-th to 1/17-th for the edges, see Figure 10. For INSthe isomorphic subgraphs turn out to be sparse, although the average densityof the graphs increases with their size. The runtime of the matching approachincreases due to the higher runtime of the Kuhn-Munkres matching algorithmon larger subgraphs, as Figure 11 shows.
The product graph approach has been tested on the same test suites for connected node-induced isomorphic subgraphs. The runtime is above that ofthe matching approach on the graphs from the Roma library, and takes about25 seconds for graphs with 50 nodes. It is about the same for sparse and fordense graphs and grows quadratically with the size of the input graph due to thequadratic growth of the square graph. In contrast, the runtime of the matchingapproach heavily depends on the density and seems to grow cubic with thenumber of neighbors due to the Bron-Kerbosch matching algorithm. It takes350 seconds on dense graphs with 50 nodes and 500 edges on the average. Itshould be noted that the absolute runtimes on a 650 MHz PC are due to theprogramming styles and are slowed down by the general-purpose data structurefor graphs from Graphlet.
On the first three test suites the product graph algorithm is inferior to the matching approach, both in the size of the detected isomorphic subgraphs and inthe run time, as Figures 8 and 9 show. The picture changes for our test suite ofdense graphs. Here the product graph algorithm finds node-induced subgraphswith about 10% more nodes and edges for each subgraph than the matchingheuristic, and the product graph algorithm is significantly faster, see Figures 10and 11. Notice that the largest graphs from this suite have 50 nodes and 500edges on the average from which 86 appear in the two isomorphic copies. Thecomparisons in Figures 8 and 10 show the numbers of nodes and edges of thecomputed isomorphic node-induced subgraphs, from which we can estimate thedensity resp. sparsity of the isomorphic subgraphs.
Drawing Isomorphic Subgraphs
In this section we consider graphs with a pair of isomorphic subgraphs and theirdrawings. Sometimes classical graph drawing algorithms preserve isomorphicsubgraphs and display them symmetrically. The Reingold and Tilford algorithm[10, 34] computes the tree drawing bottom-up, and so preserves isomorphicsubtrees rooted at distinct nodes. It is readily seen that this is no more truefor arbitrary subtrees. To stress this point, Supowit and Reingold [36] haveintroduced the notion of eumorphous tree drawings. However, eumorphous treedrawings of minimal width and integral coordinates are NP-hard. The radialtree algorithm of Eades [13] squeezes a subtree into a sector with a wedgein proportion to the number of the leaves of the subtree. Hence, isomorphic S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) edges in the matching approach nodes in the matching approach edges in the square graph approach nodes in the square graph approach number of nodes and edges in every subgraph number of nodes in the graph Figure 10: Comparison of the approaches on the dense graphs matching approach square graph approach number of nodes in the graph Figure 11: Run time of the approaches on the dense graphs S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) subtrees get the same wedge and are drawn identically up to translation androtation.
It is well-known that spring algorithms tend to display symmetric struc- tures. This comes from the nature of spring methods, and has been emphasizedby Eades and Lin [14]. For planar graphs there are efficient algorithms for thedetection and display of symmetries of the whole graphs [23, 22, 24]. Hierar-chical graphs (DAGs) can be drawn with a symmetry by a modified barycenteralgorithm [15] and by using a dominance drawing [11] if the graphs are planarand planar and reduced. For arbitrary hierarchical graphs symmetry preservingdrawing algorithms are yet unknown.
The problem of drawing symmetric structures can be solved by a three- phase method, which is generally applicable in this framework. If a graph Gis partitioned into two isomorphic subgraphs H1 and H2 and a remainder R,first construct a drawing of H1 and take a copy as a drawing of H2. Then H1and H2 are replaced by two large nodes and the remainder together with thetwo large nodes is drawn by some algorithm in phase two. This algorithm musttake the area of the large nodes into account. And it should take care of theedges entering the graphs H1 and H2. Finally, the drawings of H1 and H2 areinserted at the large nodes and the remaining edges to the nodes of H1 and H2are locally routed on the area of the large nodes.
The drawback of this approach is the third phase. The difficulties lie in the routing of the edges to the nodes of H1 and H2. This may lead to bad drawingswith many node-edge crossings and parallel edges.
The alternative to the three-phase method is an integrated approach. Here the preservation of isomorphic subgraphs is built into the drawing algorithms.
As said before, this is achieved automatically by some tree drawing algorithms,and is solved here for a spring embedder. Spring algorithms have been intro-duced to graph drawing by Eades [12]. Fruchterman and Reingold [18] havesimplified the forces to improve the running time, which is a critical factor forspring algorithms. Our algorithm is based on the advanced USE algorithm [16],which is included in the Graphlet system and is an extension of GEM [17]. Inparticular, USE supports individual distance parameters between any pair ofnodes. Other spring algorithms allow only a uniform distance.
Our goal is identical drawings of isomorphic subgraphs. The input is an undirected graph G and two isomorphic subgraphs H1 and H2 of G togetherwith the isomorphism φ from the nodes of H1 to the nodes of H2. If v2 = φ(v1)then v2 is the copy of v1.
In the initial phase, the nodes of H1 and H2 are placed identically on grid points (up to a translation). Thereafter the spring algorithm averages the forcesimposed on each node and its copy and moves both simultaneously by the samevector.
This guarantees that H1 and H2 are drawn identically, if they are isomorphic subgraphs. The placement of pairs of nodes (v, φ(v)) remains thesame, even if H1 and H2 are not isomorphic and are disconnected.
Large isomorphic subgraphs should be emphasized. They should be sepa- rated from each other and distinguished from the remainder. The distinctioncan be achieved by a node coloring. This does not help if there is no geometric S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) separation between H1 and H2, which can be enforced by imposing a strongerrepelling force between the nodes of H1 and H2. We use three distance pa-rameters, k1 for the inner subgraph distance, k2 between H1 and H2, and k3otherwise, with k1 < k3 < k2. Additionally, H1 and H2 are moved in oppositedirections by move subgraph(H1, f

) and move subgraph(H2, −f

). The force f

is the sum of the forces acting on the subgraph H1 and an extra repellingforce between the barycenters of the placements of H1 and H2.
In a round, all nodes of G are selected in random order and are moved according to the emanating forces. The algorithm stops if a certain terminationcriterion is accomplished. This is a complex formula with a cooling schedulegiven by the USE algorithm, see [16, 17]. The extra effort for the computation offorces between nodes and their copies leads to a slow down of the USE algorithmby a factor of about 1.5, if the symmetry of isomorphic subgraphs is enforced.
Input: a graph G and its partition into two isomorphic subgraphs H1
and H2, and a remainder R, and the isomorphism φ : H1 → H2
Initial placement(H1, H2)
while (termination is not yet accomplished) do forall nodes at random (v, V (G)) do f = force(v);if (v ∈ V (H1) ∪ V (H2)) then f
= force(φ(v));f = f+f
move node(φ(v), f ); move node(v, f ); move subgraph(H1, f

); move subgraph(H2, −f

); Figure 12: Isomorphism preserving spring embedder.
Figure 12 describes the main steps of the isomorphism preserving spring algorithm. For each node v, force(v) is the sum of the forces acting on v andmove node(v,f ) applies the computed forces f to a single node v.
The examples shown below are computed by the heuristic and drawn by the spring algorithm. Nice drawings of graphs come from the second and third testsuites, see Figures 13 and 14. More drawings can be found in [2] or by usingthe algorithm in Graphlet.
We wish to thank the anonymous referees for their useful comments and con-structive criticism.
S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) Figure 13: A graph of test suite 2. The original graph with 50 vertices and 76edges was copied and then 2 edges were added. Our algorithm has re-computedthe isomorphic edge-induced subgraphs.
Figure 14: Graph (number 06549 in [35]) from test suite 3 with 45 nodes, andthe computed isomorphic edge-induced subgraphs.
S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) [1] S. Bachl. Isomorphic subgraphs. In Proc. Graph Drawing'99, volume 1731 of LNCS, pages 286–296, 1999.
[2] S. Bachl. Erkennung isomorpher Subgraphen und deren Anwendung beim Zeichnen von Graphen.
at Passau, 2001.
[3] T. Biedl, J. Marks, K. Ryall, and S. Whitesides. Graph multidrawing: Finding nice drawings without defining nice. In Proc. Graph Drawing'98,volume 1547 of LNCS, pages 347–355. Springer Verlag, 1998.
[4] I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo. The maxi- mum clique problem, volume 4 of Handbook of Combinatorial Optimization.
Kluwer Academic Publishers, Boston, MA, 1999.
[5] F. J. Brandenburg.
Symmetries in graphs.
Dagstuhl Seminar Report, 98301:22, 1998.
[6] F. J. Brandenburg. Pattern matching problems in graphs. Unpublished manuscript, 2000.
[7] C. Bron and J. Kerbosch. Algorithm 457 - finding all cliques in an undi- rected graph. Comm. ACM, 16:575–577, 1973.
[8] H.-L. Chen, H.-I. Lu, and H.-C. Yen. On maximum symmetric subgraphs.
In Proc. Graph Drawing'00, volume 1984 of LNCS, pages 372–383, 2001.
[9] J. Clark and D. Holton. Graphentheorie – Grundlagen und Anwendungen.
Spektrum Akademischer Verlag, Heidelberg, 1991.
[10] G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Englewood Cliffs,NJ, 1999.
[11] G. Di Battista, R. Tamassia, and I. G. Tollis.
Area requirements and symmetry display of planar upwards drawings. Discrete Comput. Geom.,7:381–401, 1992.
[12] P. Eades. A heuristic for graph drawing. In Cong. Numer., volume 42, pages 149–160, 1984.
[13] P. Eades. Drawing free trees. Bulletin of the Institute for Combinatorics and its Applications, 5:10–36, 1992.
[14] P. Eades and X. Lin. Spring algorithms and symmetry. Theoret. Comput. Sci., 240:379–405, 2000.
[15] P. Eades, X. Lin, and R. Tamassia. An algorithm for drawing a hierarchical graph. Int. J. Comput. Geom. & Appl., 6:145–155, 1996.
S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) [16] M. Forster. Zeichnen ungerichteter graphen mit gegebenen knotengr¨ durch ein springembedder- verfahren. Diplomarbeit, Universit¨ [17] A. Frick, A. Ludwig, and H. Mehldau. A fast adaptive layout algorithm for undirected graphs. In Proc. Graph Drawing'94, volume 894 of LNCS,pages 388–403, 1995.
[18] T. Fruchterman and E. M. Reingold. Graph drawing by force-directed placement. Software – Practice and Experience, 21:1129–1164, 1991.
[19] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, 1979.
[20] D. Gmach. Erkennen von isomorphen subgraphen mittels cliquensuche im produktgraph. Diplomarbeit, Universit¨ at Passau, 2003.
[21] A. Gupta and N. Nishimura. The complexity of subgraph isomorphism for classes of partial k-trees. Theoret. Comput. Sci., 164:287–298, 1996.
[22] S.-H. Hong and P. Eades. A linear time algorithm for constructing maxi- mally symmetric straight-line drawings of planar graphs. In Proc. GraphDrawing'04, volume 3383 of LNCS, pages 307–317, 2004.
[23] S.-H. Hong and P. Eades. Symmetric layout of disconnected graphs. In Proc. ISAAC 2005, volume 2906 of LNCS, pages 405–414, 2005.
[24] S.-H. Hong, B. McKay, and P. Eades. Symmetric drawings of triconnected planar graphs. In Proc. 13 ACM-SIAM Symposium on Discrete Algorithms,pages 356–365, 2002.
[25] I. Koch. Enumerating all connected maximal common subgraphs in two graphs. Theoret. Comput. Sci., 250:1–30, 2001.
[26] G. Levi. A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo, 9:341–352, 1972.
[27] A. Lubiw.
Some np-complete problems similar to graph isomorphism.
SIAM J. Comput., 10:11–21, 1981.
[28] J. Manning. Computational complexity of geometric symmetry detection in graphs. In LNCS, volume 507 of LNCS, pages 1–7, 1990.
[29] J. Manning. Geometric symmetry in graphs. PhD thesis, Purdue Univ., isosubgraph. University of Passsau.
[31] H. Purchase. Which aesthetic has the greatest effect on human understand- ing. In Proc. Graph Drawing'97, volume 1353 of LNCS, pages 248–261,1997.
S. Bachl et. al., Isomorphic Subgraphs, JGAA, 8(2) 215–238 (2004) [32] H. Purchase, R. Cohen, and M. James. Validating graph drawing aesthetics.
In Proc. Graph Drawing'95, volume 1027 of LNCS, pages 435–446, 1996.
[33] R. C. Read and R. J. Wilson. An Atlas of Graphs. Clarendon Press Oxford, [34] E. M. Reingold and J. S. Tilford. Tidier drawings of trees. IEEE Trans. SE, 7:223–228, 1981.
[35] Roma graph library. http://www.inf.uniroma3.it/people/gdb/wp12/ LOG.html. University of Rome 3.
[36] K. J. Supowit and E. M. Reingold. The complexity of drawing trees nicely.
Acta Informatica, 18:377–392, 1983.
[37] J. R. Ullmann. An algorithm for subgraph isomorphism. J. Assoc. Comput. Mach., 16:31–42, 1970.

Source: http://jgaa.info/accepted/2004/BachlBrandenburgGmach2004.8.2.pdf