Computing and Drawing Isomorphic SubgraphsBachl, Sabine and Brandenburg, Franz J. (2002) Computing and Drawing Isomorphic Subgraphs. In: Graph Drawing 10th International Symposium, GD 2002, August 2628, 2002 , pp. 7485(Official URL: http://dx.doi.org/10.1007/3540361510_8). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540361510_8
AbstractThe isomorphic subgraph problem is finding two disjoint subgraphs of a graph which coincide on at least k edges. Then the graph partitions into a large subgraph, its copy and a remainder. The problem resembles the NPhard largest common subgraph problem. In [1,2] it has been shown that the isomorphic subgraph problem is NPhard, even for restricted instances. In this paper we present a greedy heuristic for the approximation of large isomorphic subgraphs and introduce a spring algorithm which preserves isomorphic subgraphs and displays them as copies of each other. The heuristic has been tested extensively on four independent test suites. The drawing algorithm yields nice drawings which cannot be obtained by standard spring algorithms.
Actions (login required)
