Computing and Drawing Isomorphic Subgraphs

Bachl, Sabine and Brandenburg, Franz J. (2002) Computing and Drawing Isomorphic Subgraphs. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 74-85 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_8).

Full text not available from this repository.

Abstract

The 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 NP-hard largest common subgraph problem. In [1,2] it has been shown that the isomorphic subgraph problem is NP-hard, 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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_8
Classifications:G Algorithms and Complexity > G.999 Others
M Methods > M.400 Force-directed / Energy-based
ID Code:271

Repository Staff Only: item control page

References

S. Bachl. Isomorphic subgraphs. Proc. Graph Drawing '99, LNCS 1731 (1999), 286-296.

S. Bachl. Erkennung isomorpher Subgraphen und deren Anwendung beim Zeichnen von Graphen , Dissertation, University of Passau, (2001), http://elib.ub.uni-passau.de/index.html.

L. Babai and L. Kucera. Canonical labelling of graphs in average linear time. Proc. 20th IEEE FOCS (1979), 39-46.

G. Di Battista, P. Eades, R. Tamassia and I.G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, (1999).

T. Biedl, J. Marks, K. Ryall, and S. Whitesides. Graph multidrawing: Finding nice drawings without defining nice. Proc. Graph Drawing'98, LNCS 1547 (1998), 347-355.

F.J. Brandenburg. Pattern matching problems in graphs. Unpublished manuscript, (2000).

H.-L. Chen, H.-I. Lu and H.-C. Yen. On maximum symmetric subgraphs. Proc. Graph Drawing'00, LNCS 1984 (2001), 372-383.

J. Clark and D. Holton. Graphentheorie - Grundlagen und Anwendungen. Spektrum Akademischer Verlag, (1991).

D. Corneil and D. Kirkpatrick. A theortical analysis of various heuristics for the graph isomorphism problem. SIAM J. Comput. 9, (1980), 281-297.

P. Eades. Drawing free trees. Bulletin of the Institute for Combinatorics and its Applications 5, (1992), 10-36.

P. Eades. A heuristic for graph drawing. Cong. Numer. 42, (1984), 149-160.

P. Eades and X. Lin. Spring algorithms and symmetry. Theoret. Comput. Sci. 240 (2000), 379-405.

M. Forster. Zeichnen ungerichteter Graphen mit gegebenen Knotengröße durch ein Springembedder-Verfahren. Diplomarbeit, Universität Passau, (1999).

A. Frick, A. Ludwig and M. Mehldau. A fast adaptive layout algorithm for undirected graphs. Proc. Graph Drawing '94, LNCS 894 (1995), 388-403.

T. Fruchterman and M.E. Reingold. Graph Drawing by force-directed placement. Software-Practice and Experience 21, (1991), 1129-1164.

M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, (1979).

A. Gupta and N. Nishimura. The complexity of subgraph isomorphism for classes of partial k-trees. Theoret. Comput. Sci. 164, (1996), 287-298.

S.-H. Hong, B. McKay and P. Eades. Symmetric drawings of triconnected planar graphs. Proc. 13 ACM-SIAM Symposium on Discrete Algorithms (2002), 356-365.

I. Koch. Enumerating all connected maximal common subgraphs in two graphs. Theoret. Comput. Sci. 250, (2001), 1-30.

G. Levi. A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo 9, (1972), 341-352.

A. Lubiw. Some NP-complete problems similar to graph isomorphism. SIAM J. Comput. 10, (1981), 11-21.

J. Manning, Geometric symmetry in graphs. Ph.D. thesis, Purdue Univ., (1990).

J. Manning. Computational complexity of geometric symmetry detection in graphs. LNCS 507, (1990), 1-7.

Passau Test Suite. http://www.infosun.uni-passau.de/br/isosubgraph.

H. Purchase, R. Cohen and M. James. Validating graph drawing aesthetics. Proc. Graph Drawing '95, LNCS 1027 (1996), 435-446.

H. Purchase. Which aesthetic has the greatest effect on human understanding. Proc. Graph Drawing '97, LNCS 1353 (1997), 248-261.

R.C. Read and R.J. Wilson. An Atlas of Graphs. Clarendon Press Oxford (1998).

Roma Graph Library. http://www.inf.uniroma3.it/people/gdb/wp12/LOG.html.

E.M. Reingold and J.S. Tilford. Tidier drawings of trees. IEEE Trans. SE 7, (1981), 223-228.

K.J. Supowit and E.M. Reingold. The complexity of drawing trees nicely. Acta Informatica 18, (1983), 377-392.

J.R. Ullmann. An algorithm for subgraph isomorphism. J. Assoc. Comput. Mach. 16, (1970), 31-42.