Maximizing Maximal Angles for Plane Straight-Line Graphs

Details Maximizing Maximal Angles for Plane Straight-Line Graphs Maximizing Maximal Angles for Plane Straight-Line Graphs

2007-05-25

arxiv.org/abs/0705.3820v2

In "Algorithms and Data Structures, WADS 2007, Halifax, Canada, August 15-17, 2007", Frank Dehne et al. (Eds.), LNCS 4619, Spr

Computer Science

Computational Geometry

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

Scientific paper

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

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

Affiliated with

Also associated with

No associations

Rating

Maximizing Maximal Angles for Plane Straight-Line Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximizing Maximal Angles for Plane Straight-Line Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximizing Maximal Angles for Plane Straight-Line Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-680545