## 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 ﬁnding 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 diﬀerent 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 deﬁning 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 diﬀerent 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 reﬂectional invariant. Geometric symmetriesof graphs correspond to special automorphisms, which has been elaborated in[14]. Geometric symmetries have ﬁrst 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 ﬂexibility 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 ﬁrst been investigated in [1, 2]. Theisomorphic subgraph problem is ﬁnding two large disjoint subgraphs of a givengraph, such that one subgraph is a copy of the other. Thus a graph

*G *partitionsinto

*G *=

*H*1 +

*H*2 +

*R*, where

*H*1 and

*H*2 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 diﬀerence 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 ﬂexible 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 ﬁnding a partitioninto three components,

*H*1

*, H*2, and a remainder

*R*, and an isomorphism pre-serving matching between the subgraphs

*H*1 and

*H*2. 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 diﬀerent 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 diﬀerent seeds. This approachcaptures both the partition and the isomorphism problems. Our experimentsare directed towards the appropriateness of the approach and the eﬀectivenessof 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 diﬀerent 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 deﬁne 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 diﬀerent algorithms which have been evaluated and comparedin several versions and on diﬀerent 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

*v*is 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 conﬁrm.

**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

*v*and

*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*
*H*2

*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*
*H*2

*with at least k edges?*
For INS and IES the graph

*G *partitions into two isomorphic subgraphs

*H*1
and

*H*2 and a remainder

*R *such that

*G *=

*H*1 +

*H*2 +

*R*. When computing iso-morphic subgraphs the subgraphs

*H*1 and

*H*2 are supposed to be connected andmaximal. IES is our most ﬂexible 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 × m*grid graph with

*n, m *even. If

*V*1 consists of all even nodes in the odd rows andof all odd nodes in the even rows, and

*V*2 =

*V V*1, then

*V*1 and

*V*2 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 G*2 =

(

*V *2

*, E*2)

*, whose nodes are the pairs of distinct nodes of G with V *2 =

*{*(

*u, v*)

* u *=

*v and u, v ∈ V }. The edges of G*2

*are generating or stabilizing edges betweenpairwise distinct nodes u*1

*, v*1

*, u*2

*, v*2

*. *((

*u*1

*, u*2)

*, *(

*v*1

*, v*2))

*is a generating edge, ifboth *(

*u*1

*, v*1)

*and *(

*u*2

*, v*2)

*are edges of E. *((

*u*1

*, u*2)

*, *(

*v*1

*, v*2))

*is a stabilizing edge,if there are no such edges in E. There is no edge in G*2

*, 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

*G*2, 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

*G*2 be the graph and its square. Use the

*Y *-axis for

the axial symmetry of

*G*2. For each pair of nodes

*u, v ∈ V *with

*u *=

*v *there is a

pair of symmetric nodes of

*G*2 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

*v*1

*, v*2

*, v*3

*, v*4 are distinct nodes of

*V *, then the edges induced by these

nodes in

*G*2 are symmetric, mapping ((

*v*1

*, v*2)

*, *(

*v*3

*, v*4)) to ((

*v*2

*, v*1)

*, *(

*v*4

*, v*3)).

*2*
The usability of square graphs for the computation of isomorphic subgraphs
is based on the following fact.

**Theorem 1 ***Let V*1

*and V*2

*be subsets of the set of nodes V of a graph G.*
*H*1 =

*G*[

*V*1]

*and H*2 =

*G*[

*V*2]

*are isomorphic disjoint node-induced subgraphs withan isomorphism φ *:

*V*1

*→ V*2

*if and only if the set of nodes {*(

*v, φ*(

*v*))

* v ∈ V*1

*}induces a clique in the square graph G*2

*. The isomorphism φ can be retrievedfrom the clique.*
**Proof: **If

*φ *is an isomorphism from

*H*1 into

*H*2, then for nodes

*u, v ∈ V*1 with

*u *=

*v *the nodes (

*u, φ*(

*u*)) and (

*v, φ*(

*v*)) are connected in

*G*2 by a generating edgeor by a stabilizing edge. Hence, the set of nodes

*{*(

*v, φ*(

*v*))

* v ∈ V*1

*} *induces aclique in

*G*2. Conversely, suppose that a set of nodes

*W *of

*G*2 deﬁnes a clique.

Let

*V*1 =

*{v*1

* *(

*v*1

*, v*2)

*∈ W } *and

*V*2 =

*{v*2

* *(

*v*1

*, v*2)

*∈ W } *be the projectionsonto the ﬁrst and second components. If (

*u*1

*, u*2) and (

*v*1

*, v*2) are nodes of

*W *,then the nodes

*u*1

*, v*1

*, u*2

*, v*2 are pairwise distinct. Hence

*V*1

*∩ V*2 =

*∅*. Deﬁne

*φ *:

*V*1

*→ V*2 by

*φ*(

*v*1) =

*v*2 if (

*v*1

*, v*2)

*∈ W *. From the distinctness

*φ *is a bijection.

Moreover, for nodes

*u*1

*, v*1

*∈ V*1 and their images

*u*2

*, v*2

*∈ V*2 either there aretwo edges (

*u*1

*, v*1) and (

*u*2

*, v*2) in

*G *or these pairs of nodes are not adjacent.

Hence,

*G*[

*V*1] and

*G*[

*V*2] are isomorphic disjoint node-induced subgraphs.

Consequently, a maximal clique in the node square graph

*G*2 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

*G*2 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 *=

*{a*1

*, . . , a*3

*m} *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 3

*m *fans, where the

*i*-th fan is a chain of

*s*(

*ai*) nodes which are all connected to

*v*1. 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

*v*2. The fans of

*R *are called

*B*-fans. Let

*k *= 2

*Bm − *3

*m*. Then

*G *has 2

*k *+ 2

*m *+ 1 edges.

Now

*G *has an IES solution of size

*k *if and only if there is a solution of
First, let

*A*1

*, . . , Am *be a solution of 3-partition with each

*Ai *containing
three elements of

*A*. Deﬁne

*H*1 =

*L *and

*H*2 =

*R *and a bijection

*φ *:

*H*1

*→ H*2,such that

*v*1 is mapped to

*v*2 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

*H*1 and

*H*2
(2

*s*(

*a*)

*− *1) = 2

*Bm − *3

*m *=

*k *common edges and IES has a solution.

Conversely, let

*H*1 and

*H*2 be a solution of IES with

*k *= 2

*Bm − *3

*m*. 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 2

*m *+ 1 edges go lost by the mapping. Inparticular,

*φ*(

*v*1) =

*v*2, since the degree of

*v*1 and

*v*2 is

*Bm *+ 1, whereas allother nodes have a degree of at most three. Hence, if

*φ*(

*v*1)

=

*v*2, then at least2

*· *(

*Bm *+ 1

*− *3) edges go lost and at most

* E − *2(

*Bm − *2) edges are left for

*H*1and

*H*2. Since

* E *= 4

*Bm − *4

*m *+ 1 and

*B > *1, less than

*k − *3 edges are leftfor each of

*H*1 and

*H*2, contradicting the assumption

*φ*(

*v*1) =

*v*2. Let

*v*1 be in

*H*1 and

*v*2 in

*H*2. If the subgraphs must be connected, then

*H*1 is a subgraphof

*L *and

*H*1 =

*L *to achieve the bound

*k*, and similarly

*H*2 is a subgraph of

*R*.

This is also true, if

*H*1 and

*H*2 may be disconnected. To see this suppose thecontrary. If

*j > *0 edges of

*R *are in

*H*1, then at least

*j *+ 1 nodes of

*R *are in

*H*1. Each such node decreases the number of edges for the isomorphic copies atleast by one, since the edges to

*v*2 go lost. And for every three

*s*(

*ai*)-fans from

*L *at least two edges from

*R *go lost. Since

*R *has

*k *+ 2

*m *edges,

*j *= 0,

*H*1 =

*L*and

*H*2 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

*B*4

*< s*(

*a*)

*< B*2 ,
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 *= 3

*Bm − *6

*m*.

The left subgraph

*L *consists of 3

*m *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

*v*1.

The right subgraph

*R *has

*m *fans where each fan has exactly

*B *+ (

*B − *1) nodesand the nodes at odd positions are connected to

*v*2. The nodes

*v*1 and

*v*2 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

*H*1 and

*H*2, with

*k *edges each, and which may beconnected or not if and only if

*H*1 =

*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 *= 3

*Bm − *3

*m*. 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 diﬀerent heuristics for the computation of max-imal connected isomorphic subgraphs. The isomorphic subgraph problem isdiﬀerent 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 ﬁrst 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

*H*1 and

*H*2 have been computedas copies of each other. For each pair of new nodes (

*v*1

*, v*2) not in

*H*1 and

*H*2the following graph parameters are taken into account:

*• w*1 = degree(

*v*1)+degree(

*v*2)

*• w*2 =

*− *degree(

*v*1)

*−*degree(

*v*2)

* *
*• w*3 =

*−*(the number of common neighbors)

*• w*4 = the number of new neighbors of

*v*1 and

*v*2 which are not in

*H*1

*∪ H*2

*• w*5 = the graph theoretical distance between

*v*1 and

*v*2

*• w*6 = the number of new isomorphic edges in (

*H*1

*∪ v*1

*, H*2

*∪ v*2).

These parameters can be combined arbitrarily to a weight

*W *=

*λiwi *with
0

*≤ λi ≤ *1. Observe that

*w*2 and

*w*3 are taken negative. Let

*w*0 =
The greedy algorithm proceeds as follows: Suppose that

*H*1 and

*H*2 are
disjoint connected isomorphic subgraphs which have been computed so far andare identiﬁed by the mapping

*φ *:

*V*1

*→ V*2 on their sets of nodes. The algorithmselects the next pair of nodes (

*u*1

*, u*2)

*∈ V*1

*× V*2 with

*u*2 =

*φ*(

*u*1) 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

*u*1 and

*u*2. For each such pair (

*v*1

*, v*2) of neighbors of (

*u*1

*, u*2) with

*v*1

*, v*2

*∈ V*1

*∪ V*2 and

*v*1

=

*v*2 there is an edge with weight

*W *(

*v*1

*, v*2) =

*wi*, where

*wi *is any of the above weighting functions. For example,

*W *(

*v*1

*, v*2) is the sumof the degrees of

*v*1 and

*v*2 for

*w*1. There is no edge if

*v*1 =

*v*2. Then computean optimal weighted bipartite matching. For the matching we have used theKuhn-Munkres algorithm (Hungarian method) [9] with a runtime of

*O*(

*n*2

*m*).

In decreasing order by the weight of the matching edges the pairs of matchednodes (

*v*1

*, v*2) are taken for an extension of

*H*1 and

*H*2, provided that (

*v*1

*, v*2)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 (

*v*1

*, v*2) is added to the
pair of isomorphic subgraphs if the isomorphism can be extended by

*v*1 and

*v*2.

Otherwise

*v*1 and

*v*2 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 if

*u*1 and

*u*2 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*(

*n*3

*m*). 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

*w*1(3

*, *6) +

*w*1(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, ﬁrst 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 ﬁnds 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 identiﬁed by
S. Bachl et. al.,

*Isomorphic Subgraphs*, JGAA, 8(2) 215–238 (2004)
Figure 4: The matching approach
initialize(

*P *);while (

*P *=

*∅*) do
(

*u*1

*, u*2) = next(P); delete (

*u*1

*, u*2) from

*P *;

*N*1 = new neighbors of

*u*1;

*N*2 = new neighbors of

*u*2;

*M *= optimal weighted bipartite matching over

*N*1 and

*N*2;forall edges(

*v*1

*, v*2) of

*M *decreasingly by their weight do
if

*G*[

*V*1

*∪ {v*1

*}*] is isomorphic to

*G*[

*V*2

*∪ {v*2

*}*] then

*P *=

*P ∪ {*(

*v*1

*, v*2)

*}*;

*V*1 =

*V*1

*∪ {v*1

*}*;

*V*2 =

*V*2

*∪ {v*2

*}*;
Figure 5: The matching approach for isomorphic node-induced subgraphs.

the isomorphism.

In our experiments a single parameter

*wi *or the sum

*w*0 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*(

*n*2) 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*(

*n*2) 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 classiﬁed 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 diﬀerent 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

*G*2 is a generating edge with weight

*w*(

*e*) =

* V *2 or astabilizing edge of weight

*w*(

*e*) = 1. For a set of nodes

*X *deﬁne 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

*G*2 = (

*X, E*) of

*G*;Select two adjacent nodes

*v*1 and

*v*2 such that

*wX*(

*{v*1

*, v*2

*}*) is maximal;

*C *=

*{v*1

*, v*2

*}*;

*U *=

*N*(

*v*1)

*∩ N*(

*v*2);
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 ﬁve times with diﬀerent 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

*G*2 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 ﬁrst 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 reﬂected 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

*· n*2 edges, with ﬁve 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 ﬁrst three testsuites give a uniform picture. It ﬁnds the optimal subgraphs in the ﬁrst 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

*w*2,

*w*3 and

*w*6 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

*w*0,

*w*1,

*w*4 and

*w*5 on a 750 MHz PC with 256 MBRAM, 30 seconds for

*w*2 and 100 seconds for

*w*3 and

*w*6, since in the latter casesthe algorithm iterates over almost all pairs of starting nodes. In summary, thediﬀerence of degree weight

*w*2 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

*w*2performs 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

*w*2 ﬁnds 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 ﬁrst 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 ﬁnds node-induced subgraphswith about 10% more nodes and edges for each subgraph than the matchingheuristic, and the product graph algorithm is signiﬁcantly 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 eﬃcient 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 modiﬁed 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

*G*is partitioned into two isomorphic subgraphs

*H*1 and

*H*2 and a remainder

*R*,ﬁrst construct a drawing of

*H*1 and take a copy as a drawing of

*H*2. Then

*H*1and

*H*2 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

*H*1 and

*H*2. Finally, the drawings of

*H*1 and

*H*2 areinserted at the large nodes and the remaining edges to the nodes of

*H*1 and

*H*2are locally routed on the area of the large nodes.

The drawback of this approach is the third phase. The diﬃculties lie in the
routing of the edges to the nodes of

*H*1 and

*H*2. 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] havesimpliﬁed 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

*H*1 and

*H*2 of

*G *togetherwith the isomorphism

*φ *from the nodes of

*H*1 to the nodes of

*H*2. If

*v*2 =

*φ*(

*v*1)then

*v*2 is the copy of

*v*1.

In the initial phase, the nodes of

*H*1 and

*H*2 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

*H*1 and

*H*2 are drawn identically, if they are
isomorphic subgraphs. The placement of pairs of nodes (

*v, φ*(

*v*)) remains thesame, even if

*H*1 and

*H*2 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

*H*1 and

*H*2, which can be enforced by imposing a strongerrepelling force between the nodes of

*H*1 and

*H*2. We use three distance pa-rameters,

*k*1 for the inner subgraph distance,

*k*2 between

*H*1 and

*H*2, and

*k*3otherwise, with

*k*1

*< k*3

*< k*2. Additionally,

*H*1 and

*H*2 are moved in oppositedirections by

*move subgraph*(

*H*1

*, f*) and

*move subgraph*(

*H*2

*, −f*). The force

*f *is the sum of the forces acting on the subgraph

*H*1 and an extra repellingforce between the barycenters of the placements of

*H*1 and

*H*2.

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 eﬀort 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

*H*1

and

*H*2, and a remainder

*R*, and the isomorphism

*φ *:

*H*1

*→ H*2

Initial placement(

*H*1

*, H*2)

while (termination is not yet accomplished) do
forall nodes at random (

*v, V *(

*G*)) do

*f *= force(

*v*);if (

*v ∈ V *(

*H*1)

*∪ V *(

*H*2)) then

*f *= force(

*φ*(

*v*));

*f *=

*f*+

*f*
move node(

*φ*(

*v*)

*, f *);
move node(

*v, f *);
move subgraph(

*H*1

*, f*); move subgraph(

*H*2

*, −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 *and

*move 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 deﬁning 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 - ﬁnding 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 Cliﬀs,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 eﬀect 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

Bae HK, et al. • Korean J Pediatr 2016;59(6):262270http://dx.doi.org/10.3345/kjp.2016.59.5.262pISSN 1738-1061•eISSN 2092-7258 The effect of sildenafil on right ventricular remo deling in a rat model of monocrotalineinduced right ventricular failureHyun Kyung Bae, MD1, Hyeryon Lee, PhD1, Kwan Chang Kim, MD, PhD2, Young Mi Hong, MD, PhD1Departments of 1Pediatrics, 2Thoracic and Cardiovascular Surgery, Ewha Womans University School of Medicine, Seoul, Korea

Available online at www.sciencedirect.com Research in Veterinary Science 85 (2008) 26–34 Cushing's disease in dogs: Cabergoline treatment V.A. Castillo *, N.V. Go´mez, J.C. Lalia, M.F. Cabrera Blatter, J.D. Garcı´a Hospital Escuela-Unidad de Endocrinologı´a, A. Clı´nica Me´dica de Pequen˜os Animales, Fac. de Ciencias Veterinarias-UBA, Av. Chorroarin 280, 1427 C. Buenos Aires, Argentina