A new upper bound for angular resolution

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)^{\frac{1}{2}}/d^{\frac...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-09
Main Author: Miyata, Hiroyuki
Format: Article
Language:English
Subjects:
Angular resolution
Graph theory
Graphs
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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)^{\frac{1}{2}}/d^{\frac{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 \(\varepsilon\), we construct a family of planar graphs with maximum degree \(d\) that have angular resolution \(O((\log d)^\varepsilon/d^{\frac{3}{2}})\) in any planar straight-line drawing.
ISSN:2331-8422