Maximizing Maximal Angles for Plane Straight-Line Graphs

Authors:

Abstract: Let

G = (S, E)

be a plane straight-line graph on a finite point set

S s u b s e t R^{2}

in general position. The incident angles of a vertex

p i n S

of

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

p h i

-open if each vertex has an incident angle of size at least

p h i

. In this paper we study the following type of question: What is the maximum angle

p h i

such that for any finite set

S s u b s e t R^{2}

of points in general position we can find a graph from a certain class of graphs on

S

that is

p h i

-open? In particular, we consider the classes of triangulations, spanning trees, and paths on

S

and give tight bounds in most cases.

Recommendations

Cited In (4)

This page was built for publication: Maximizing Maximal Angles for Plane Straight-Line Graphs