On Maximum Symmetric Subgraphs

Chen, Ho-Lin and Lu, Hsueh-I. and Yen, Hsu-Chun (2001) On Maximum Symmetric Subgraphs. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 372-383 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_35).

Full text not available from this repository.


Let G be an n-node graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting edges, and contracting edges. This NP-complete problem arises naturally from the objective of drawing G as symmetrically as possible. We show that its tractability for the special cases of G being a plane graph, an ordered tree, and an unordered tree, depends on the type of operations used to obtain H from G. Moreover, we give an $O(\log n)$-approximation algorithm for the intractable case that H is obtained from a tree G by contracting edges. As a by-product, we give an $O(\log n)$-approximation algorithm for an NP-complete edit-distance problem.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_35
Classifications:G Algorithms and Complexity > G.910 Symmetries
G Algorithms and Complexity > G.999 Others
ID Code:432

Repository Staff Only: item control page


T. Akutsu, An RNC algorithm for finding a largest common subtree of two trees, IEICE Transactions on Information Systems, E75-D, pp. 95-101, 1992.

S. Bachl, Isomorphic Subgraphs, International Symposium on Graph DRawing (GD'99), LNCS 1731, pp. 286-296, 1999.

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

K. Chin and H. Yen, The Symmetry Number Problem for Trees, manuscript, 1998.

F. de Fraysseix, A Heuristic for Graph Symmetry Detection, International Symposium on Graph Drawing (GD'99), LNCS 1731, pp. 276-285, 1999.

P. Eades and X. Lin, Spring Algorithms and Symmetry, Computing and Combinatorics (COCOON'97), LNCS 1276, pp. 202-211, 1997.

M. Garey and D. Johnson, Computers and Intractability: A guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979.

S. Hong, P. Eades, and S. Lee, Finding Planar Geometric Automorphismus in Planar Graphs, 9th International Symposium on Algorithms and Computation (ISAAC'98) LNCS 1533, Springer, pp. 277-286, 1998.

S. Hong, P. Eades, A. Quigley, and S. Lee, Drawing Algorithms for Series Parallel Digraphs in Tree Dimensions, International Symposium on Graph Drawing (GD'98), LNCS 1547, pp. 198-209, 1998.

S. Hong, P. Eades, A. Quigley, and S. Lee, Drawing Series-Parallel Digraphs Symmetrically, manuscript, 1999.

J. Hopcroft and R. Tarjan, A V^2 Algorithm for Determining Isomorphism of Planar Graphs, Information Processing Letters, 1(1):32-34, 1971.

P. Kilpeleinen, and H. Mannila, Ordered and Unordered Tree Inclusion, SIAM Journal on Computing 24(2):340-356, 1995.

P. Klein, Computing the Edit Distance Between Unrooted Ordered Trees, 6th European Symposium on Algorithms (ESA '98), LNCS 1461, 91-102, 1998.

E. Lawer, Combinatorial Optimization: Networks and Matroids, New York: Holt, Rinehart & Winston, 1976.

J. Manning, Geometric Symmetry in Graphs, Ph.D. Dissertation, Department of Computer Science, Purdue University, 1990.

J. Manning and M. Atallah. Fast Detection and Display of Symmetry in Trees, Congressus Numerantium, 64:159-169, 1988.

University, 1990.

J. Manning and M. Atallah, K. Cudjoe, J. Lozito, and R. Pacheco. A System for Drawing Graphs with Geometric Symmetry, International Symposium on Graph Drawing (GD '95), LNCS 894, pp. 262-265, 1995.

C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

K. Zhang, and T. Jiang, Some MAX SNP-hard Results Concerning Unordered Labeled Trees, Information Processing Letters 49(5):249-254, 1994.

K. Zhang, and D. Shasha, Simple Fast Algorithms for the Editing Distance between Trees and Related Problems, SIAM Journal on Computing 18(6):1245-1262, 1989.