Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Tenth International Symposium on Graph Drawing, GD 2002
DOI: 10.7155/jgaa.00090
Computing and Drawing Isomorphic Subgraphs
Vol. 8, no. 2, pp. 215-238, 2004. Regular paper.
Abstract The isomorphic subgraph problem is finding two disjoint subgraphs of a
graph which coincide on at least k edges. The graph is partitioned into
a subgraph, its copy, and a remainder. The problem resembles the NP-hard
largest common subgraph problem, which searches copies of a graph in a
pair of graphs. In this paper we show that the isomorphic subgraph
problem is NP-hard, even for restricted instances such as connected
outerplanar graphs. Then we present two different heuristics for the
computation of maximal connected isomorphic subgraphs. Both heuristics use
weighting functions and have been tested on four independent test suites.
Finally, we introduce a spring algorithm which preserves isomorphic
subgraphs and displays them as copies of each other. The drawing algorithm
yields nice drawings and emphasizes the isomorphic subgraphs.
|
Journal Supporters
|