Metrics#
Crossings#
Metric |
Description |
Source |
Implementation |
---|---|---|---|
Crossings |
A list of all crossings |
Purchase et al. [PCJ96] |
|
Crossing number |
Number of crossings |
Purchase et al. [PCJ96] |
|
Crossing density |
The total number of crossings divided by the number of possible crossings |
Mooney et al. [MPWK24] |
|
Crossing angles |
A list of all angles between pairwise crossing edges |
Coleman and Parker [CP96] |
|
Crossing angular resolution |
The minimum angle formed between two pair-wise crossing edges |
Coleman and Parker [CP96] |
Area and boundary#
Metric |
Description |
Source |
Implementation |
---|---|---|---|
Area |
The size of an axis-aligned rectangular bounding box |
Taylor and Rodgers [TR05] |
|
Tight area |
The size of the convex hull of the graph |
Taylor and Rodgers [TR05] |
|
Height |
Height of the graph |
||
Width |
Width of the graph |
||
Aspect ratio |
The proportion between the smaller and the bigger side of the axis-aligned rectangular bounding box containing the graph |
Taylor and Rodgers [TR05] |
Node distribution#
Metric |
Description |
Source |
Implementation |
---|---|---|---|
Center of mass |
The average position of all nodes, optionally weighted by supplying a weight vector. |
||
Closest pair of points |
The closest pair of nodes in the drawing |
Burch [Bur15] |
|
Closest pair of elements |
The closest pair of graph elements, i.e. points and line segments. |
Burch [Bur15] |
|
Concentration |
Indicates how evenly nodes are spread among the bounding box |
Taylor and Rodgers [TR05] |
|
Homogeneity |
Measure of how evenly nodes are distributed among the four quadrants between 0 and 1. A value of 0 indicates an even distribution among the four quadrants. |
Taylor and Rodgers [TR05] |
|
Horizontal balance |
Returns a value between -1 and 1 indicating the horizontal balance. A value of 0 means a perfectly even balance between the upper and lower half. A value of -1 means that all nodes lie on the lower half, a value of 1 means that all nodes lie on the upper half. |
Tamassia et al. [TDBB88] |
|
Vertical balance |
Returns a value between -1 and 1 indicating the vertical balance. A value of 0 means a perfectly even balance between the left and right half. A value of -1 means that all nodes lie on the left half, a value of 1 means that all nodes lie on the right half. |
Tamassia et al. [TDBB88] |
|
Node orthogonality |
A measure of how much the nodes align in a grid. |
Purchase [Pur02] |
|
Gabriel ratio |
The Gabriel ratio is defined as the percentage of nodes falling within a minimum circle covering an edge for any edge. |
Mooney et al. [MPWK24] |
Edge directions#
Metric |
Description |
Source |
Implementation |
---|---|---|---|
Angular resolution |
The angular resolution is defined as the minimum angle between two edges incident to the same vertex. |
Coleman and Parker [CP96] |
|
Average flow |
The average edge direction of a directed graph. |
Bennett et al. [BRSG07] |
|
Upwards flow |
This measures the percentage of edges pointing ’upwards’, meaning that the angle between the edge and the upward vector is strictly smaller than 90°. Only defined for directed graphs. |
Purchase [Pur02] |
|
Coherence to average flow |
The upwards flow with the average flow as the ’upwards’ direction. Only defined for directed graphs. |
Purchase [Pur02] |
|
Edge orthogonality |
A measure of the extend to which the edge are vertically or horizontally aligned. |
Purchase [Pur02] |
Symmetry#
Metric |
Description |
Source |
Implementation |
---|---|---|---|
Node-based symmetry |
This metric tries to estimate reflective symmetry by checking for symmetry axes along each pair of nodes. |
Purchase [Pur02] |
|
Edge-based symmetry |
A metric for estimating either reflective, rotational or translational symmetry. |
Klapaukh et al. [KMP18] |
|
Stress-based symmetry |
As the stress of a graph has been shown to correlate with symmetry, this metric simply calculates the stress of the given graph. |
Welch and Kobourov [WK17] |
|
Even neighborhood distribution |
This metric estimates how evenly the neighborhood of each vertex is distributed around the barycenter of the neighborhood. |
Xu et al. [XYG18] |
|
Visual symmetry |
Given the time complexity of the previous symmetry metrics, this metric draws an image of the graph and estimates symmetry in a pixel-based manner. |
Bibliography#
Chris Bennett, Jody Ryall, Leo Spalteholz, and Amy Gooch. The aesthetics of graph visualization. Computational Aesthetics in Graphics, 2007. doi:10.2312/COMPAESTH/COMPAESTH07/057-064.
Michael Burch. The aesthetics of diagrams. In Proceedings of the 6th International Conference on Information Visualization Theory and Applications - Volume 1: IVAPP, (VISIGRAPP 2015), 262–267. INSTICC, SciTePress, 2015. doi:10.5220/0005357502620267.
Michael K. Coleman and D. Stott Parker. Aesthetics-based Graph Layout for Human Consumption. Software: Practice and Experience, 26(12):1415–1438, December 1996.
Felice De Luca, Stephen Kobourov, and Helen Purchase. Perception of Symmetries in Drawings of Graphs. In Therese Biedl and Andreas Kerren, editors, Graph Drawing and Network Visualization, volume 11282, pages 433–446. Springer International Publishing, Cham, 2018. doi:10.1007/978-3-030-04414-5_31.
Roman Klapaukh, Stuart Marshall, and David Pearce. A Symmetry Metric for Graphs and Line Diagrams. In Peter Chapman, Gem Stapleton, Amirouche Moktefi, Sarah Perez-Kriz, and Francesco Bellucci, editors, Diagrammatic Representation and Inference, volume 10871, pages 739–742. Springer International Publishing, Cham, 2018. doi:10.1007/978-3-319-91376-6_71.
A. Meidiana, S.-H. Hong, P. Eades, and D. Keim. Automorphism Faithfulness Metrics for Symmetric Graph Drawings. IEEE Transactions on Visualization and Computer Graphics, pages 1–15, 2022. URL: https://ieeexplore.ieee.org/document/9987696/ (visited on 2023-12-10), doi:10.1109/TVCG.2022.3229354.
Gavin J. Mooney, Helen C. Purchase, Michael Wybrow, and Stephen G. Kobourov. The multi-dimensional landscape of graph drawing metrics. In 17th IEEE Pacific Visualization Symposium. Pacific Visualization 2024, 2024.
Helen C. Purchase. Metrics for Graph Drawing Aesthetics. Journal of Visual Languages & Computing, 13(5):501–516, October 2002. doi:10.1006/jvlc.2002.0232.
Helen C. Purchase, Robert F. Cohen, and Murray James. Validating graph drawing aesthetics. In Franz J. Brandenburg, editor, Graph Drawing, 435–446. Berlin, Heidelberg, 1996. Springer Berlin Heidelberg.
R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man, and Cybernetics, 18(1):61–79, 1988. doi:10.1109/21.87055.
M. Taylor and P. Rodgers. Applying graphical design techniques to graph visualisation. In Ninth International Conference on Information Visualisation (IV'05), 651–656. IEEE, 2005. doi:10.1109/IV.2005.19.
E. Welch and S. Kobourov. Measuring Symmetry in Drawings of Graphs. Computer Graphics Forum, 36(3):341–351, June 2017. doi:10.1111/cgf.13192.
Taihua Xu, Jie Yang, and Guanglei Gou. A Force-Directed Algorithm for Drawing Directed Graphs Symmetrically. Mathematical Problems in Engineering, 2018:1–24, November 2018. doi:10.1155/2018/6208509.