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.