TY - GEN

T1 - On vertex- and empty-ply proximity drawings

AU - Angelini, Patrizio

AU - Chaplick, Steven

AU - De Luca, Felice

AU - Fiala, Jiří

AU - Hančl, Jaroslav

AU - Heinsohn, Niklas

AU - Kaufmann, Michael

AU - Kobourov, Stephen

AU - Kratochvíl, Jan

AU - Valtr, Pavel

N1 - Publisher Copyright:
© Springer International Publishing AG 2018.

PY - 2018

Y1 - 2018

N2 - We initiate the study of the vertex-ply of straight-line drawings, as a relaxation of the recently introduced ply number. Consider the disks centered at each vertex with radius equal to half the length of the longest edge incident to the vertex. The vertex-ply of a drawing is determined by the vertex covered by the maximum number of disks. The main motivation for considering this relaxation is to relate the concept of ply to proximity drawings. In fact, if we interpret the set of disks as proximity regions, a drawing with vertex-ply number 1 can be seen as a weak proximity drawing, which we call empty-ply drawing. We show non-trivial relationships between the ply number and the vertex-ply number. Then, we focus on empty-ply drawings, proving some properties and studying what classes of graphs admit such drawings. Finally, we prove a lower bound on the ply and the vertex-ply of planar drawings.

AB - We initiate the study of the vertex-ply of straight-line drawings, as a relaxation of the recently introduced ply number. Consider the disks centered at each vertex with radius equal to half the length of the longest edge incident to the vertex. The vertex-ply of a drawing is determined by the vertex covered by the maximum number of disks. The main motivation for considering this relaxation is to relate the concept of ply to proximity drawings. In fact, if we interpret the set of disks as proximity regions, a drawing with vertex-ply number 1 can be seen as a weak proximity drawing, which we call empty-ply drawing. We show non-trivial relationships between the ply number and the vertex-ply number. Then, we focus on empty-ply drawings, proving some properties and studying what classes of graphs admit such drawings. Finally, we prove a lower bound on the ply and the vertex-ply of planar drawings.

UR - http://www.scopus.com/inward/record.url?scp=85041863745&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041863745&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-73915-1_3

DO - 10.1007/978-3-319-73915-1_3

M3 - Conference contribution

AN - SCOPUS:85041863745

SN - 9783319739144

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 24

EP - 37

BT - Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers

A2 - Ma, Kwan-Liu

A2 - Frati, Fabrizio

PB - Springer-Verlag

T2 - 25th International Symposium on Graph Drawing and Network Visualization, GD 2017

Y2 - 25 September 2017 through 27 September 2017

ER -