Maximizing maximal angles for plane straight-line graphs

O. Aichholzer; T. Hackl; M. Hoffmann; C. Huemer; A. Pór; F. Santos; B. Speckmann; B. Vogtenhuber

doi:10.1007/978-3-540-73951-7_40

Maximizing maximal angles for plane straight-line graphs

O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, A. Pór, F. Santos, B. Speckmann, B. Vogtenhuber

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

7 Citations (Scopus)

100 Downloads (Pure)

Abstract

Let G¿=¿(S, E) be a plane straight-line graph on a finite point set in general position. The incident angles of a point p¿¿¿S in G are the angles between any two edges of G that appear consecutively in the circular order of the edges incident to p. A plane straight-line graph is called ¿-open if each vertex has an incident angle of size at least ¿. In this paper we study the following type of question: What is the maximum angle ¿ such that for any finite set of points in general position we can find a graph from a certain class of graphs on S that is ¿-open? In particular, we consider the classes of triangulations, spanning trees, and paths on S and give tight bounds in most cases.

Original language	English
Title of host publication	Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada
Editors	F. Dehne, J.R. Sack, N. Zeh
Place of Publication	Berlin
Publisher	Springer
Pages	458-469
ISBN (Print)	978-3-540-73948-7
DOIs	https://doi.org/10.1007/978-3-540-73951-7_40
Publication status	Published - 2007
Event	10th International Symposium on Algorithms and Data Structures (WADS 2007) - Halifax, Canada Duration: 15 Aug 2007 → 17 Aug 2007 Conference number: 10

Publication series

Name	Lecture Notes in Computer Science
Volume	4619
ISSN (Print)	0302-9743

Conference

Conference	10th International Symposium on Algorithms and Data Structures (WADS 2007)
Abbreviated title	WADS 2007
Country/Territory	Canada
City	Halifax
Period	15/08/07 → 17/08/07
Other	WADS 2007, Halifax, Nova Scotia, Canada

Access to Document

10.1007/978-3-540-73951-7_40

Metis210768Final published version, 476 KB

Cite this

Aichholzer, O., Hackl, T., Hoffmann, M., Huemer, C., Pór, A., Santos, F., Speckmann, B., & Vogtenhuber, B. (2007). Maximizing maximal angles for plane straight-line graphs. In F. Dehne, J. R. Sack, & N. Zeh (Eds.), Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada (pp. 458-469). (Lecture Notes in Computer Science; Vol. 4619). Springer. https://doi.org/10.1007/978-3-540-73951-7_40

@inproceedings{f4c589a1f6644dbeb64f4f79b0eefdf1,

title = "Maximizing maximal angles for plane straight-line graphs",

abstract = "Let G¿=¿(S, E) be a plane straight-line graph on a finite point set in general position. The incident angles of a point p¿¿¿S in G are the angles between any two edges of G that appear consecutively in the circular order of the edges incident to p. A plane straight-line graph is called ¿-open if each vertex has an incident angle of size at least ¿. In this paper we study the following type of question: What is the maximum angle ¿ such that for any finite set of points in general position we can find a graph from a certain class of graphs on S that is ¿-open? In particular, we consider the classes of triangulations, spanning trees, and paths on S and give tight bounds in most cases.",

author = "O. Aichholzer and T. Hackl and M. Hoffmann and C. Huemer and A. P{\'o}r and F. Santos and B. Speckmann and B. Vogtenhuber",

year = "2007",

doi = "10.1007/978-3-540-73951-7_40",

language = "English",

isbn = "978-3-540-73948-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "458--469",

editor = "F. Dehne and J.R. Sack and N. Zeh",

booktitle = "Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada",

address = "Germany",

note = "10th International Symposium on Algorithms and Data Structures (WADS 2007), WADS 2007 ; Conference date: 15-08-2007 Through 17-08-2007",

}

Aichholzer, O, Hackl, T, Hoffmann, M, Huemer, C, Pór, A, Santos, F, Speckmann, B & Vogtenhuber, B 2007, Maximizing maximal angles for plane straight-line graphs. in F Dehne, JR Sack & N Zeh (eds), Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada. Lecture Notes in Computer Science, vol. 4619, Springer, Berlin, pp. 458-469, 10th International Symposium on Algorithms and Data Structures (WADS 2007), Halifax, Nova Scotia, Canada, 15/08/07. https://doi.org/10.1007/978-3-540-73951-7_40

Maximizing maximal angles for plane straight-line graphs. / Aichholzer, O.; Hackl, T.; Hoffmann, M. et al.

Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada. ed. / F. Dehne; J.R. Sack; N. Zeh. Berlin : Springer, 2007. p. 458-469 (Lecture Notes in Computer Science; Vol. 4619).

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

TY - GEN

T1 - Maximizing maximal angles for plane straight-line graphs

AU - Aichholzer, O.

AU - Hackl, T.

AU - Hoffmann, M.

AU - Huemer, C.

AU - Pór, A.

AU - Santos, F.

AU - Speckmann, B.

AU - Vogtenhuber, B.

N1 - Conference code: 10

PY - 2007

Y1 - 2007

N2 - Let G¿=¿(S, E) be a plane straight-line graph on a finite point set in general position. The incident angles of a point p¿¿¿S in G are the angles between any two edges of G that appear consecutively in the circular order of the edges incident to p. A plane straight-line graph is called ¿-open if each vertex has an incident angle of size at least ¿. In this paper we study the following type of question: What is the maximum angle ¿ such that for any finite set of points in general position we can find a graph from a certain class of graphs on S that is ¿-open? In particular, we consider the classes of triangulations, spanning trees, and paths on S and give tight bounds in most cases.

AB - Let G¿=¿(S, E) be a plane straight-line graph on a finite point set in general position. The incident angles of a point p¿¿¿S in G are the angles between any two edges of G that appear consecutively in the circular order of the edges incident to p. A plane straight-line graph is called ¿-open if each vertex has an incident angle of size at least ¿. In this paper we study the following type of question: What is the maximum angle ¿ such that for any finite set of points in general position we can find a graph from a certain class of graphs on S that is ¿-open? In particular, we consider the classes of triangulations, spanning trees, and paths on S and give tight bounds in most cases.

U2 - 10.1007/978-3-540-73951-7_40

DO - 10.1007/978-3-540-73951-7_40

M3 - Conference contribution

SN - 978-3-540-73948-7

T3 - Lecture Notes in Computer Science

SP - 458

EP - 469

BT - Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada

A2 - Dehne, F.

A2 - Sack, J.R.

A2 - Zeh, N.

PB - Springer

CY - Berlin

T2 - 10th International Symposium on Algorithms and Data Structures (WADS 2007)

Y2 - 15 August 2007 through 17 August 2007

ER -

Aichholzer O, Hackl T, Hoffmann M, Huemer C, Pór A, Santos F et al. Maximizing maximal angles for plane straight-line graphs. In Dehne F, Sack JR, Zeh N, editors, Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada. Berlin: Springer. 2007. p. 458-469. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-73951-7_40

Maximizing maximal angles for plane straight-line graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this