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 of n-vertex graphs is O(n2)×O(n2), as shown by Bárány and Rote by means of a sophisticated technique based on perturbing (non strictly) convex drawings. Unfortunately, the constants hidden in this area bound are in the order of 104. 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) × (2n3 − n2).
STRICTLY CONVEX DRAWINGS OF 3-CONNECTED PLANAR GRAPHS
Montecchiani F.;
2024
Abstract
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 of n-vertex graphs is O(n2)×O(n2), as shown by Bárány and Rote by means of a sophisticated technique based on perturbing (non strictly) convex drawings. Unfortunately, the constants hidden in this area bound are in the order of 104. 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) × (2n3 − n2).File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
