



























Abstract:A well-known result by Kant [Algorithmica, 1996] implies that $n$-vertex outerplane graphs admit embedding-preserving planar straight-line grid drawings where the internal faces are convex polygons in $O(n^{2})$ area. In this paper, we present an algorithm to compute such drawings in $O(n^{1.5})$ area. We also consider outerplanar drawings in which the internal faces are required to be strictly-convex polygons. In this setting, we provide a $\Theta(nk^2)$ area bound for $n$-vertex outerplanar graphs whose weak dual is a path and whose maximum face size is $k$ and a $\Theta(nd^2)$ area bound for $n$-vertex outerplanar graphs whose diameter is bounded by $d$.
From: Fabrizio Frati [view email]
[v1]
Wed, 27 Aug 2025 14:19:24 UTC (447 KB)
[v2]
Mon, 20 Jul 2026 09:21:07 UTC (768 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。