Metrics#

Crossings#

Metric	Description	Source	Implementation
Crossings	A list of all crossings	Purchase et al. [PCJ96]	`crossings.get_crossings()`
Crossing number	Number of crossings	Purchase et al. [PCJ96]	`crossings.number_of_crossings()`
Crossing density	The total number of crossings divided by the number of possible crossings	Mooney et al. [MPWK24]	`crossings.crossing_density()`
Crossing angles	A list of all angles between pairwise crossing edges	Coleman and Parker [CP96]	`crossings.crossing_angles()`
Crossing angular resolution	The minimum angle formed between two pair-wise crossing edges	Coleman and Parker [CP96]	`crossings.crossing_angular_resolution()`

Area and boundary#

Metric	Description	Source	Implementation
Area	The size of an axis-aligned rectangular bounding box	Taylor and Rodgers [TR05]	`boundary.area()`
Tight area	The size of the convex hull of the graph	Taylor and Rodgers [TR05]	`boundary.area_tight()`
Height	Height of the graph		`boundary.height()`
Width	Width of the graph		`boundary.width()`
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]	`boundary.aspect_ratio()`

Node distribution#

Metric	Description	Source	Implementation
Center of mass	The average position of all nodes, optionally weighted by supplying a weight vector.		`distribution.center_of_mass()`
Closest pair of points	The closest pair of nodes in the drawing	Burch [Bur15]	`distribution.closest_pair_of_points()`
Closest pair of elements	The closest pair of graph elements, i.e. points and line segments.	Burch [Bur15]	`distribution.closest_pair_of_elements()`
Concentration	Indicates how evenly nodes are spread among the bounding box	Taylor and Rodgers [TR05]	`distribution.concentration()`
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]	`distribution.homogeneity()`
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]	`distribution.horizontal_balance()`
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]	`distribution.vertical_balance()`
Node orthogonality	A measure of how much the nodes align in a grid.	Purchase [Pur02]	`distribution.node_orthogonality()`
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]	`distribution.gabriel_ratio()`

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]	`edge_directions.angular_resolution()`
Average flow	The average edge direction of a directed graph.	Bennett et al. [BRSG07]	`edge_directions.average_flow()`
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]	`edge_directions.upwards_flow()`
Coherence to average flow	The upwards flow with the average flow as the ’upwards’ direction. Only defined for directed graphs.	Purchase [Pur02]	`edge_directions.coherence_to_average_flow()`
Edge orthogonality	A measure of the extend to which the edge are vertically or horizontally aligned.	Purchase [Pur02]	`edge_directions.edge_orthogonality()`

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]	`symmetry.reflective_symmetry()`
Edge-based symmetry	A metric for estimating either reflective, rotational or translational symmetry.	Klapaukh et al. [KMP18]	`symmetry.edge_based_symmetry()`
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]	`symmetry.stress()`
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]	`symmetry.even_neighborhood_distribution()`
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.		`symmetry.visual_symmetry()`

Bibliography#

[BRSG07]

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.

[Bur15] (1,2)

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.

[CP96] (1,2,3)

Michael K. Coleman and D. Stott Parker. Aesthetics-based Graph Layout for Human Consumption. Software: Practice and Experience, 26(12):1415–1438, December 1996.

[DLKP18]

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.

[KMP18]

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.

[MHEK22]

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.

[MPWK24] (1,2)

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.

[Pur02] (1,2,3,4,5)

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.

[PCJ96] (1,2)

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.

[TDBB88] (1,2)

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.

[TR05] (1,2,3,4,5)

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.

[WK17]

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.

[XYG18]

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.