Isomorphic Subgraphs

Bachl, Sabine (1999) Isomorphic Subgraphs. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999 , pp. 286-296(Official URL: http://dx.doi.org/10.1007/3-540-46648-7_30).

Full text not available from this repository.

Abstract

We are interested in finding symmetries in graphs and then use these symmetries for graph drawing algorithms. There are two general approaches to this problem, the first one is known as GEOMETRIC SYMMETRIES on the basis of drawings, the other rests upon the graph-theoretical notion of graphs. For a given graph G the ISOMORPHIC SUBGRAPHS problem makes use of the second approach and tries to find the two largest disjoint isomorphic subgraphs in G. Hence, G consists of two identical copies and a remainder. There are many NP-complete or open problems related to our problem, like GRAPH ISOMORPHISM, GRAPH AUTOMORPHISM or LARGEST COMMON SUBGRAPH. We show that the ISOMORPHIC SUBGRAPHS problem is NP-hard for connected outerplanar graphs, and 2-connected planar graphs and is solvable in linear time when restricted to trees. Additionally we will shortly discuss the applicability of ISOMORPHIC SUBGRAPHS in graph drawing algorithms.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-46648-7_30
Classifications: G Algorithms and Complexity > G.910 Symmetries
G Algorithms and Complexity > G.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/357

Actions (login required)

View Item View Item