2024/10/15 by David Eppstein, Michael T. Goodrich, Eppstein, David +3
Computer Science · Engineering · #68R10 #Advanced Graph Theory Research #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.m #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2410.12083
openalex publication_date 2024/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study algorithms for drawing planar graphs and 1-planar graphs using cubic Bézier curves with bounded curvature. We show that any n-vertex 1-planar graph has a 1-planar RAC drawing using a single cubic Bézier curve per edge, and this drawing can be computed in O(n) time given a combinatorial 1-planar drawing. We also show that any n-vertex planar graph G can be drawn in O(n) time with a single cubic Bézier curve per edge, in an O(n)× O(n) bounding box, such that the edges have Θ(1/degree(v)) angular resolution, for each v ∈ G, and O(√(n)) curvature.