| Maximizing Maximal Angles for Plane Straight Line Graphs (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Let G =(S, E) be a plane straight line graph on a finite point set S ⊂ R 2 in general position. For a point p ∈ S let the maximum incident angle of p in G be the maximum angle 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 S ⊂ R 2 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. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||