Special Issue on Selected Papers from the 11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017
An Experimental Study on the Ply Number of Straight-line Drawings
Vol. 23, no. 1, pp. 71-91, 2019. Regular paper.
Abstract The ply number of a drawing is a new criterion of interest for graph drawing. Informally, the ply number of a straight-line drawing of a graph is defined as the maximum number of overlapping disks, where each disk is associated with a vertex and has a radius that is half the length of the longest edge incident to that vertex. This paper reports the results of an extensive experimental study that attempts to estimate correlations between the ply number and other aesthetic quality metrics for a graph layout, such as stress, edge-length uniformity, and edge crossings. We also investigate the performance of several graph drawing algorithms in terms of ply number, and provide new insights into the theoretical gap between lower and upper bounds on the ply number of $k$-ary trees.
Submitted: September 2017.
Reviewed: June 2018.
Revised: June 2018.
Reviewed: August 2018.
Revised: August 2018.
Accepted: August 2018.
Final: August 2018.
Published: January 2019.
article (PDF)