zbMATH — the first resource for mathematics

An interactive tool to explore and improve the ply number of drawings. (English) Zbl 07026976
Frati, Fabrizio (ed.) et al., Graph drawing and network visualization. 25th international symposium, GD 2017, Boston, MA, USA, September 25–27, 2017. Revised selected papers. Cham: Springer (ISBN 978-3-319-73914-4/pbk; 978-3-319-73915-1/ebook). Lecture Notes in Computer Science 10692, 38-51 (2018).
Summary: Given a straight-line drawing \(\varGamma\) of a graph \(G=(V,E)\), for every vertex \(v\) the ply disk \(D_v\) is defined as a disk centered at \(v\) where the radius of the disk is half the length of the longest edge incident to \(v\). The ply number of a given drawing is defined as the maximum number of overlapping disks at some point in \(\mathrm{I\!R}^2\). Here we present a tool to explore and evaluate the ply number for graphs with instant visual feedback for the user. We evaluate our methods in comparison to an existing ply computation by De Luca et al. [WALCOM’17]. We are able to reduce the computation time from seconds to milliseconds for given drawings and thereby contribute to further research on the ply topic by providing an efficient tool to examine graphs extensively by user interaction as well as some automatic features to reduce the ply number.
For the entire collection see [Zbl 1381.68007].
68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
apfloat; OGDF; Ply; yFiles
Full Text: DOI