On vertex- and empty-ply proximity drawings

Patrizio Angelini; Steven Chaplick; Felice De Luca; Jiří Fiala; Jaroslav Hančl; Niklas Heinsohn; Michael Kaufmann; Stephen Kobourov; Jan Kratochvíl; Pavel Valtr

doi:10.1007/978-3-319-73915-1_3

On vertex- and empty-ply proximity drawings

Patrizio Angelini, Steven Chaplick, Felice De Luca, Jiří Fiala, Jaroslav Hančl, Niklas Heinsohn, Michael Kaufmann, Stephen Kobourov, Jan Kratochvíl, Pavel Valtr

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers
Editors	Kwan-Liu Ma, Fabrizio Frati
Publisher	Springer-Verlag
Pages	24-37
Number of pages	14
ISBN (Print)	9783319739144
DOIs	https://doi.org/10.1007/978-3-319-73915-1_3
State	Published - 2018
Externally published	Yes
Event	25th International Symposium on Graph Drawing and Network Visualization, GD 2017 - Boston, United States Duration: Sep 25 2017 → Sep 27 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10692 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	25th International Symposium on Graph Drawing and Network Visualization, GD 2017
Country/Territory	United States
City	Boston
Period	9/25/17 → 9/27/17

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Angelini, P., Chaplick, S., De Luca, F., Fiala, J., Hančl, J., Heinsohn, N., Kaufmann, M., Kobourov, S., Kratochvíl, J., & Valtr, P. (2018). On vertex- and empty-ply proximity drawings. In K.-L. Ma, & F. Frati (Eds.), Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers (pp. 24-37). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10692 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-319-73915-1_3

On vertex- and empty-ply proximity drawings. / Angelini, Patrizio; Chaplick, Steven; De Luca, Felice et al.
Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers. ed. / Kwan-Liu Ma; Fabrizio Frati. Springer-Verlag, 2018. p. 24-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10692 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Angelini, P, Chaplick, S, De Luca, F, Fiala, J, Hančl, J, Heinsohn, N, Kaufmann, M, Kobourov, S, Kratochvíl, J & Valtr, P 2018, On vertex- and empty-ply proximity drawings. in K-L Ma & F Frati (eds), Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10692 LNCS, Springer-Verlag, pp. 24-37, 25th International Symposium on Graph Drawing and Network Visualization, GD 2017, Boston, United States, 9/25/17. https://doi.org/10.1007/978-3-319-73915-1_3

Angelini P, Chaplick S, De Luca F, Fiala J, Hančl J, Heinsohn N et al. On vertex- and empty-ply proximity drawings. In Ma KL, Frati F, editors, Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers. Springer-Verlag. 2018. p. 24-37. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-73915-1_3

Angelini, Patrizio ; Chaplick, Steven ; De Luca, Felice et al. / On vertex- and empty-ply proximity drawings. Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers. editor / Kwan-Liu Ma ; Fabrizio Frati. Springer-Verlag, 2018. pp. 24-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6c58a731790543f9b4bb5d47b14cf8c9,

title = "On vertex- and empty-ply proximity drawings",

abstract = "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.",

author = "Patrizio Angelini and Steven Chaplick and {De Luca}, Felice and Ji{\v r}{\'i} Fiala and Jaroslav Han{\v c}l and Niklas Heinsohn and Michael Kaufmann and Stephen Kobourov and Jan Kratochv{\'i}l and Pavel Valtr",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2018.; 25th International Symposium on Graph Drawing and Network Visualization, GD 2017 ; Conference date: 25-09-2017 Through 27-09-2017",

year = "2018",

doi = "10.1007/978-3-319-73915-1_3",

language = "English (US)",

isbn = "9783319739144",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "24--37",

editor = "Kwan-Liu Ma and Fabrizio Frati",

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

}

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

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 -

On vertex- and empty-ply proximity drawings

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this