arXiv Open Access 2022

Strictly-Convex Drawings of $3$-Connected Planar Graphs

Michael A. Bekos Martin Gronemann Fabrizio Montecchiani Antonios Symvonis

Lihat Sumber

Abstrak

Strictly-convex straight-line drawings of $3$-connected planar graphs in small area form a classical research topic in Graph Drawing. Currently, the best-known area bound for such drawings is $O(n^2) \times O(n^2)$, as shown by Bárány and Rote by means of a sophisticated technique based on perturbing (non-strictly) convex drawings. Unfortunately, the hidden constants in such area bound are in the $10^4$ order. We present a new and easy-to-implement technique that yields strictly-convex straight-line planar drawings of $3$-connected planar graphs on an integer grid of size $2(n-1) \times (5n^3-4n^2)$.

Topik & Kata Kunci

cs.CG

Penulis (4)

Michael A. Bekos

Martin Gronemann

Fabrizio Montecchiani

Antonios Symvonis

Format Sitasi

APA MLA BibTeX

Bekos, M.A., Gronemann, M., Montecchiani, F., Symvonis, A. (2022). Strictly-Convex Drawings of $3$-Connected Planar Graphs. https://arxiv.org/abs/2208.13388

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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