Institutional Repository
| maximizing maximal angles for plane straight-line graphs | |
| Aichholzer Oswin; Hackl Thomas; Hoffmann Michael; Huemer Clemens; Por Attila; Santos Francisco; Speckmann Bettina; Vogtenhuber Birgit | |
| 2013 | |
| Source | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
 |
| ISSN | 0925-7721 |
| Volume | 46Issue:1Pages:17-28 |
| English Abstract | Let G = (S, E) be a plane straight-line graph on a finite point set S subset of R-2 in general position. The incident angles of a point p is an element of 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 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 of 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 spanning paths on S and give tight bounds in most cases. (C) 2012 Elsevier B.V. All rights reserved.; Let G = (S, E) be a plane straight-line graph on a finite point set S subset of R-2 in general position. The incident angles of a point p is an element of 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 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 of 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 spanning paths on S and give tight bounds in most cases. (C) 2012 Elsevier B.V. All rights reserved. |
| Indexed Type | SCI |
| Keyword | Plane Geometric Graph Triangulation Path Maximal Angle Pointed Plane Graph |
| Department | Speckmann Bettina TU Eindhoven Dept Math & Comp Sci Eindhoven Netherlands. Aichholzer Oswin; Hackl Thomas; Vogtenhuber Birgit Graz Univ Technol Inst Software Technol A-8010 Graz Austria. Hoffmann Michael Swiss Fed Inst Technol Inst Theoret Comp Sci Zurich Switzerland. Huemer Clemens Univ Politecn Cataluna Dept Matemat Aplicada 4 E-08028 Barcelona Spain. Por Attila Charles Univ Prague Dept Appl Math CR-11636 Prague 1 Czech Republic. Por Attila Charles Univ Prague Inst Theoret Comp Sci CR-11636 Prague 1 Czech Republic. Santos Francisco Univ Cantabria Dept Matemat Estadist & Comp Santander Spain. |
| Subject | Mathematics |
| Sponsorship | Austrian Science Fund (FWF), NRN 'Industrial Geometry S9205-N12; Austrian Science Fund (EWE) P23629-N18; project MEC MTM2009-07242; project DGR 2009SGR1040; Spanish Ministry of Science T60427, MTM2008-04699-C03-02, CSD2006-00032 |
| Language | 英语 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/15045 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Aichholzer Oswin,Hackl Thomas,Hoffmann Michael,et al. maximizing maximal angles for plane straight-line graphs[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS,2013,46(1):17-28. |
| APA | Aichholzer Oswin.,Hackl Thomas.,Hoffmann Michael.,Huemer Clemens.,Por Attila.,...&Vogtenhuber Birgit.(2013).maximizing maximal angles for plane straight-line graphs.COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS,46(1),17-28. |
| MLA | Aichholzer Oswin,et al."maximizing maximal angles for plane straight-line graphs".COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 46.1(2013):17-28. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment