On Maximum Symmetric SubgraphsChen, HoLin and Lu, HsuehI. and Yen, HsuChun (2001) On Maximum Symmetric Subgraphs. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000 , pp. 372383(Official URL: http://dx.doi.org/10.1007/3540445412_35). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540445412_35
AbstractLet G be an nnode graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting edges, and contracting edges. This NPcomplete 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 byproduct, we give an $O(\log n)$approximation algorithm for an NPcomplete editdistance problem.
Actions (login required)
