Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00090 Computing and Drawing Isomorphic Subgraphs Sabine Bachl , Franz J. Brandenburg , and Daniel Gmach 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.
|
Revised: October 2004. Submitted: April 2003. Communicated by Xin He |
| Journal of Graph Algorithms and Applications |