An experimental study on the ply number of straight-line drawings

Felice De Luca, Emilio Di Giacomo, Walter Didimo, Stephen Kobourov, Giuseppe Liotta

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)71-91
Number of pages21
JournalJournal of Graph Algorithms and Applications
Volume23
Issue number1
DOIs
StatePublished - 2019
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Computer Science Applications
  • Geometry and Topology
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'An experimental study on the ply number of straight-line drawings'. Together they form a unique fingerprint.

Cite this