Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909351406469120 |
|---|---|
| author | Eppstein, David Goodrich, Michael T. Illickan, Abraham M. |
| author_facet | Eppstein, David Goodrich, Michael T. Illickan, Abraham M. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_12083 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature Eppstein, David Goodrich, Michael T. Illickan, Abraham M. Computational Geometry 68R10 F.m 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. |
| title | Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature |
| topic | Computational Geometry 68R10 F.m |
| url | https://arxiv.org/abs/2410.12083 |