Geodesic
Computing and Drawing Isomorphic Subgraphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Tenth International Symposium on Graph Drawing, GD 2002 , Tome 8 (2004) no. 2, pp. 215-238.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2004_8_2_a5,
     author = {Sabine Bachl and Franz Brandenburg and Daniel Gmach},
     title = {Computing and {Drawing} {Isomorphic} {Subgraphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {215--238},
     publisher = {mathdoc},
     volume = {8},
     number = {2},
     year = {2004},
     doi = {10.7155/jgaa.00090},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00090/}
}
TY  - JOUR
AU  - Sabine Bachl
AU  - Franz Brandenburg
AU  - Daniel Gmach
TI  - Computing and Drawing Isomorphic Subgraphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2004
SP  - 215
EP  - 238
VL  - 8
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00090/
DO  - 10.7155/jgaa.00090
LA  - en
ID  - JGAA_2004_8_2_a5
ER  - 
%0 Journal Article
%A Sabine Bachl
%A Franz Brandenburg
%A Daniel Gmach
%T Computing and Drawing Isomorphic Subgraphs
%J Journal of Graph Algorithms and Applications
%D 2004
%P 215-238
%V 8
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00090/
%R 10.7155/jgaa.00090
%G en
%F JGAA_2004_8_2_a5
Sabine Bachl; Franz Brandenburg; Daniel Gmach. Computing and Drawing Isomorphic Subgraphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Tenth International Symposium on Graph Drawing, GD 2002
					, Tome 8 (2004) no. 2, pp. 215-238. doi : 10.7155/jgaa.00090. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00090/

Cité par Sources :