maximizing maximal angles for plane straight-line graphs

CORC > 软件研究所 > 软件所图书馆 > 期刊论文

	maximizing maximal angles for plane straight-line graphs
	Aichholzer Oswin ; Hackl Thomas ; Hoffmann Michael ; Huemer Clemens ; Por Attila ; Santos Francisco ; Speckmann Bettina ; Vogtenhuber Birgit
刊名	COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
	2013
卷号	46 期号:1 页码:17-28
关键词	Plane geometric graph Triangulation Path Maximal angle Pointed plane graph
ISSN号	0925-7721
中文摘要	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.
学科主题	Mathematics
收录类别	SCI
资助信息	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
语种	英语
公开日期	2013-09-17
内容类型	期刊论文
源URL	[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.