TY - JOUR

T1 - Maximizing maximal angles for plane straight-line graphs

AU - Aichholzer, O.

AU - Hackl, T.

AU - Hoffmann, M.

AU - Huemer, C.

AU - Santos, F.

AU - Speckmann, B.

AU - Vogtenhuber, B.

PY - 2013

Y1 - 2013

N2 - Let G=(S,E) be a plane straight-line graph on a finite point set S¿R2 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 f-open if each vertex has an incident angle of size at least f. In this paper we study the following type of question: What is the maximum angle f such that for any finite set S¿R2 of points in general position we can find a graph from a certain class of graphs on S that is f-open? In particular, we consider the classes of triangulations, spanning trees, and spanning 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 S¿R2 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 f-open if each vertex has an incident angle of size at least f. In this paper we study the following type of question: What is the maximum angle f such that for any finite set S¿R2 of points in general position we can find a graph from a certain class of graphs on S that is f-open? In particular, we consider the classes of triangulations, spanning trees, and spanning paths on S and give tight bounds in most cases.

U2 - 10.1016/j.comgeo.2012.03.002

DO - 10.1016/j.comgeo.2012.03.002

M3 - Article

VL - 46

SP - 17

EP - 28

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

IS - 1

ER -