Automorphism Faithfulness Metrics for Symmetric Graph Drawings

In this article, we present new quality metrics for symmetric graph drawing based on group theory. Roughly speaking, the new metrics are
faithfulness
metrics, i.e., they measure how faithfully a drawing of a graph displays the ground truth (i.e., geometric automorphisms) of the graph as symmetries. More specifically, we introduce two types of automorphism faithfulness metrics for displaying: (1) a single geometric automorphism as a symmetry (
axial
or
rotational
), and (2) a group of geometric automorphisms (
cyclic
or
dihedral
). We present algorithms to compute the automorphism faithfulness metrics in
$O(n \log n)$
time. Moreover, we also present efficient algorithms to detect
exact
symmetries in a graph drawing. We then validate our automorphism faithfulness metrics using deformation experiments. Finally, we use the metrics to evaluate existing graph drawing algorithms to compare how faithfully they display geometric automorphisms of a graph as symmetries.