Maximizing maximal angles for plane straight-line graphs

O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, A. Pór, F. Santos, B. Speckmann, B. Vogtenhuber

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)
76 Downloads (Pure)

Abstract

Let G¿=¿(S, E) be a plane straight-line graph on a finite point set in general position. The incident angles of a point p¿¿¿S in 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 ¿-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 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.
Original languageEnglish
Title of host publicationProceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada
EditorsF. Dehne, J.R. Sack, N. Zeh
Place of PublicationBerlin
PublisherSpringer
Pages458-469
ISBN (Print)978-3-540-73948-7
DOIs
Publication statusPublished - 2007
Event10th International Symposium on Algorithms and Data Structures (WADS 2007) - Halifax, Canada
Duration: 15 Aug 200717 Aug 2007
Conference number: 10

Publication series

NameLecture Notes in Computer Science
Volume4619
ISSN (Print)0302-9743

Conference

Conference10th International Symposium on Algorithms and Data Structures (WADS 2007)
Abbreviated titleWADS 2007
Country/TerritoryCanada
CityHalifax
Period15/08/0717/08/07
OtherWADS 2007, Halifax, Nova Scotia, Canada

Fingerprint

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

Cite this