arXiv Open Access 2024

Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature

David Eppstein Michael T. Goodrich Abraham M. Illickan

Lihat Sumber

Abstrak

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)\times O(n)$ bounding box, such that the edges have $Θ(1/degree(v))$ angular resolution, for each $v \in G$, and $O(\sqrt{n})$ curvature.

Topik & Kata Kunci

cs.CG

Penulis (3)

David Eppstein

Michael T. Goodrich

Abraham M. Illickan

Format Sitasi

APA MLA BibTeX

Eppstein, D., Goodrich, M.T., Illickan, A.M. (2024). Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature. https://arxiv.org/abs/2410.12083

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2024
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓