An integer programming approach to fuzzy symmetry detection

1 Introduction An important aim in Automatic Graph Drawing is the display of symmetric structure inherent in a graph. Empirical studies show that symmetric drawings of a graph are much easier to understand than asymmetric ones [14]. However, two different problems occur when trying to develop algorithms for symmetric graph drawing: first, the symmetry detection problem is NP-hard for general graphs [13]. Second, most graphs do not admit any exact symmetry at all; in order to create nearly symmetric drawings, one has to define some kind of relaxation of exact symmetry. For the first problem, two different algorithms with exponential runtime in general but fast runtime in practice have been proposed recently. In [4], we presented an approach based on integer programming techniques; see [5] and [3] also. Later, Abelson et al. [2] devised an algorithm based on group-theoretic methods, running even faster