TY - GEN
T1 - An experimental study on the ply number of straight-line drawings
AU - De Luca, Felice
AU - Di Giacomo, Emilio
AU - Didimo, Walter
AU - Kobourov, Stephen
AU - Liotta, Giuseppe
N1 - Funding Information:
Research supported in part by the MIUR project AMANDA “Algorithmics for MAssive and Networked DAta”, prot. 2012C4E3KT_001. Work on this problem began at the NII Shonan Meeting Big Graph Drawing: Metrics and Methods, Jan. 12–15, 2015. We thank M. Kaufmann and his staff in the University of Tübingen for sharing their code to compute ply number. We also thank A. Wolff and F. Montecchiani for many useful discussions.
Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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 numbers and other aesthetic quality metrics for a graph layout, such as stress, edge-length uniformity, and edge crossings. We also investigate the performances of several graph drawing algorithms in terms of ply number, and provides new insights on the theoretical gap between lower and upper bounds on the ply number of k-ary trees.
AB - 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 numbers and other aesthetic quality metrics for a graph layout, such as stress, edge-length uniformity, and edge crossings. We also investigate the performances of several graph drawing algorithms in terms of ply number, and provides new insights on the theoretical gap between lower and upper bounds on the ply number of k-ary trees.
UR - http://www.scopus.com/inward/record.url?scp=85014168055&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85014168055&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-53925-6_11
DO - 10.1007/978-3-319-53925-6_11
M3 - Conference contribution
AN - SCOPUS:85014168055
SN - 9783319539249
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 135
EP - 148
BT - WALCOM
A2 - Rahman, Md. Saidur
A2 - Yen, Hsu-Chun
A2 - Poon, Sheung-Hung
PB - Springer-Verlag
T2 - 11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017
Y2 - 29 March 2017 through 31 March 2017
ER -