Meidiana Amyra, Hong Seok-Hee, Eades Peter, Keim Daniel
IEEE Trans Vis Comput Graph. 2024 Jul;30(7):3241-3255. doi: 10.1109/TVCG.2022.3229354. Epub 2024 Jun 27.
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 logn) 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.
在本文中，我们基于群论提出了用于对称图绘制的新质量度量。大致而言，新度量是忠实度度量，即它们衡量图的绘制将图的基本事实（即几何自同构）作为对称性展示得有多忠实。更具体地说，我们引入了两种用于展示的自同构忠实度度量：(1) 作为对称性（轴向或旋转）的单个几何自同构，以及 (2) 一组几何自同构（循环或二面体）。我们提出了在O(n logn)时间内计算自同构忠实度度量的算法。此外，我们还提出了在图绘制中检测精确对称性的高效算法。然后，我们通过变形实验验证我们的自同构忠实度度量。最后，我们使用这些度量来评估现有的图绘制算法，以比较它们将图的几何自同构作为对称性展示得有多忠实。
