Maximizing Maximal Angles for Plane Straight-Line Graphs

Abstract

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

15 pages, 14 figures. Apart of minor corrections, some proofs that were omitted in the previous version are now included