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(n2) area. In this paper, we present an algorithm to compute such drawings in O(n1.5) area. We also consider outerplanar drawings in which the internal faces are required to be strictly-convex polygons. In this setting, we consider outerplanar graphs whose weak dual is a path and give a drawing algorithm that achieves Θ(nk2) area, where k is the maximum size of an internal facial cycle.
Bekos, M.A., Da Lozzo, G., Frati, F., Liotta, G., Symvonis, A. (2025). Internally-Convex Drawings of Outerplanar Graphs in Small Area. In Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/lipics.gd.2025.18].
Internally-Convex Drawings of Outerplanar Graphs in Small Area
Giordano Da Lozzo
;Fabrizio Frati
;
2025-01-01
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(n2) area. In this paper, we present an algorithm to compute such drawings in O(n1.5) area. We also consider outerplanar drawings in which the internal faces are required to be strictly-convex polygons. In this setting, we consider outerplanar graphs whose weak dual is a path and give a drawing algorithm that achieves Θ(nk2) area, where k is the maximum size of an internal facial cycle.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
