Gabriel triangulations and angle-monotone graphs : local routing and recognition

N. Bonichon; P. Bose; P. Carmi; I. Kostitsyna; A. Lubiw; S. Verdonschot

doi:10.1007/978-3-319-50106-2_40

Gabriel triangulations and angle-monotone graphs : local routing and recognition

N. Bonichon
, P. Bose
, P. Carmi
, I. Kostitsyna
, A. Lubiw
, S. Verdonschot

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

22 Citations (Scopus)

325 Downloads (Pure)

Abstract

A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is x- and y-monotone. Angle-monotone graphs are backslashsqrt2 -spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half- backslashtheta 6 -graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex s to any vertex t whose length is within 1 + backslashsqrt2 times the Euclidean distance from s to t. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.

Original language	English
Title of host publication	Graph Drawing and Network Visualization : 24th International Symposium., GD 2016, Athens, Greece, September 19-21, 2046. Revised Selected Papers
Editors	Yifan Hu, Martin Nöllenburg
Place of Publication	Dordrecht
Publisher	Springer
Pages	519-531
Number of pages	13
ISBN (Electronic)	978-3-319-50106-2
ISBN (Print)	978-3-319-50105-5
DOIs	https://doi.org/10.1007/978-3-319-50106-2_40
Publication status	Published - 2016
Externally published	Yes
Event	24th International Symposium on Graph Drawing and Network Visualization (GD 2016) - Athens, Greece Duration: 19 Sept 2016 → 21 Sept 2016 Conference number: 24

Publication series

Name	Lecture Notes in Computer Science
Volume	9801

Conference

Conference	24th International Symposium on Graph Drawing and Network Visualization (GD 2016)
Abbreviated title	GD 2016
Country/Territory	Greece
City	Athens
Period	19/09/16 → 21/09/16

Access to Document

10.1007/978-3-319-50106-2_40

angle_monotone_submittedFinal author version , 852 KB

Cite this

Bonichon, N., Bose, P., Carmi, P., Kostitsyna, I., Lubiw, A., & Verdonschot, S. (2016). Gabriel triangulations and angle-monotone graphs : local routing and recognition. In Y. Hu, & M. Nöllenburg (Eds.), Graph Drawing and Network Visualization : 24th International Symposium., GD 2016, Athens, Greece, September 19-21, 2046. Revised Selected Papers (pp. 519-531). (Lecture Notes in Computer Science; Vol. 9801). Springer. https://doi.org/10.1007/978-3-319-50106-2_40

Bonichon, N. ; Bose, P. ; Carmi, P. et al. / Gabriel triangulations and angle-monotone graphs : local routing and recognition. Graph Drawing and Network Visualization : 24th International Symposium., GD 2016, Athens, Greece, September 19-21, 2046. Revised Selected Papers. editor / Yifan Hu ; Martin Nöllenburg. Dordrecht : Springer, 2016. pp. 519-531 (Lecture Notes in Computer Science).

@inproceedings{9f9ab7a3f93542e998ae134000086eec,

title = "Gabriel triangulations and angle-monotone graphs : local routing and recognition",

abstract = "A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is x- and y-monotone. Angle-monotone graphs are backslashsqrt2 -spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half- backslashtheta 6 -graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex s to any vertex t whose length is within 1 + backslashsqrt2 times the Euclidean distance from s to t. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.",

author = "N. Bonichon and P. Bose and P. Carmi and I. Kostitsyna and A. Lubiw and S. Verdonschot",

year = "2016",

doi = "10.1007/978-3-319-50106-2\_40",

language = "English",

isbn = "978-3-319-50105-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "519--531",

editor = "Yifan Hu and Martin N{\"o}llenburg",

booktitle = "Graph Drawing and Network Visualization : 24th International Symposium., GD 2016, Athens, Greece, September 19-21, 2046. Revised Selected Papers",

address = "Germany",

note = "24th International Symposium on Graph Drawing and Network Visualization (GD 2016), GD 2016 ; Conference date: 19-09-2016 Through 21-09-2016",

}

Bonichon, N, Bose, P, Carmi, P, Kostitsyna, I, Lubiw, A & Verdonschot, S 2016, Gabriel triangulations and angle-monotone graphs : local routing and recognition. in Y Hu & M Nöllenburg (eds), Graph Drawing and Network Visualization : 24th International Symposium., GD 2016, Athens, Greece, September 19-21, 2046. Revised Selected Papers. Lecture Notes in Computer Science, vol. 9801, Springer, Dordrecht, pp. 519-531, 24th International Symposium on Graph Drawing and Network Visualization (GD 2016), Athens, Greece, 19/09/16. https://doi.org/10.1007/978-3-319-50106-2_40

Gabriel triangulations and angle-monotone graphs : local routing and recognition. / Bonichon, N.; Bose, P.; Carmi, P. et al.
Graph Drawing and Network Visualization : 24th International Symposium., GD 2016, Athens, Greece, September 19-21, 2046. Revised Selected Papers. ed. / Yifan Hu; Martin Nöllenburg. Dordrecht: Springer, 2016. p. 519-531 (Lecture Notes in Computer Science; Vol. 9801).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Gabriel triangulations and angle-monotone graphs : local routing and recognition

AU - Bonichon, N.

AU - Bose, P.

AU - Carmi, P.

AU - Kostitsyna, I.

AU - Lubiw, A.

AU - Verdonschot, S.

N1 - Conference code: 24

PY - 2016

Y1 - 2016

N2 - A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is x- and y-monotone. Angle-monotone graphs are backslashsqrt2 -spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half- backslashtheta 6 -graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex s to any vertex t whose length is within 1 + backslashsqrt2 times the Euclidean distance from s to t. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.

AB - A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is x- and y-monotone. Angle-monotone graphs are backslashsqrt2 -spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half- backslashtheta 6 -graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex s to any vertex t whose length is within 1 + backslashsqrt2 times the Euclidean distance from s to t. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.

U2 - 10.1007/978-3-319-50106-2_40

DO - 10.1007/978-3-319-50106-2_40

M3 - Conference contribution

SN - 978-3-319-50105-5

T3 - Lecture Notes in Computer Science

SP - 519

EP - 531

BT - Graph Drawing and Network Visualization : 24th International Symposium., GD 2016, Athens, Greece, September 19-21, 2046. Revised Selected Papers

A2 - Hu, Yifan

A2 - Nöllenburg, Martin

PB - Springer

CY - Dordrecht

T2 - 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

Y2 - 19 September 2016 through 21 September 2016

ER -

Bonichon N, Bose P, Carmi P, Kostitsyna I, Lubiw A, Verdonschot S. Gabriel triangulations and angle-monotone graphs : local routing and recognition. In Hu Y, Nöllenburg M, editors, Graph Drawing and Network Visualization : 24th International Symposium., GD 2016, Athens, Greece, September 19-21, 2046. Revised Selected Papers. Dordrecht: Springer. 2016. p. 519-531. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-50106-2_40

Gabriel triangulations and angle-monotone graphs : local routing and recognition

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this