Isomorphic SubgraphsBachl, Sabine (1999) Isomorphic Subgraphs. In: Graph Drawing 7th International Symposium, GD’99, September 1519, 1999 , pp. 286296(Official URL: http://dx.doi.org/10.1007/3540466487_30). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540466487_30
AbstractWe 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 graphtheoretical 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 NPcomplete or open problems related to our problem, like GRAPH ISOMORPHISM, GRAPH AUTOMORPHISM or LARGEST COMMON SUBGRAPH. We show that the ISOMORPHIC SUBGRAPHS problem is NPhard for connected outerplanar graphs, and 2connected 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.
Actions (login required)
