Maximizing maximal angles for plane straight line graphs

O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, F. Santos, B. Speckmann, B. Vogtenhuber

Research output: Contribution to conferenceAbstractAcademic

74 Downloads (Pure)

Abstract

Let G = (S,E) be a plane straight line graph on a finite point set S R2 in general position. For a point p 2 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 R2 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 all but one cases.
Original languageEnglish
Pages98-101
Publication statusPublished - 2007
Event23rd European Workshop on Computational Geometry (EuroCG 2007) - Graz, Switzerland
Duration: 19 Mar 200721 Mar 2007
Conference number: 23

Workshop

Workshop23rd European Workshop on Computational Geometry (EuroCG 2007)
Abbreviated titleEuroCG
CountrySwitzerland
CityGraz
Period19/03/0721/03/07

Fingerprint Dive into the research topics of 'Maximizing maximal angles for plane straight line graphs'. Together they form a unique fingerprint.

Cite this