2023/09/15 by Miyata, Hiroyuki
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2309.08401
The angular resolution of a planar straight-line drawing of a graph is the smallest angle formed by two edges incident to the same vertex. Garg and Tamassia (ESA '94) constructed a family of planar graphs with maximum degree d that have angular resolution O((log d)(1)/(2)/d(3)/(2)) in any planar straight-line drawing. This upper bound has been the best known upper bound on angular resolution for a long time. In this paper, we improve this upper bound. For an arbitrarily small positive constant ε, we construct a family of planar graphs with maximum degree d that have angular resolution O((log d)ε/d(3)/(2)) in any planar straight-line drawing.