maximizing maximal angles for plane straight-line graphs

ISCAS OpenIR

	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
发表期刊	COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
ISSN	0925-7721
卷号	46 期号:1 页码:17-28
摘要	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.
收录类别	SCI
关键词	Plane Geometric Graph Triangulation Path Maximal Angle Pointed Plane Graph
部门归属	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.
学科领域	Mathematics
资助者	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
语种	英语
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15045
专题	中国科学院软件研究所
推荐引用方式 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.