We study the upward point-set embeddability of digraphs on one-sided convex point sets with at most 1 bend per edge. We provide an algorithm to compute a 1-bend upward point-set embedding of outerplanar st-digraphs on arbitrary one-sided convex point sets. We complement this result by proving that for every n≥18 there exists a 2-outerplanar st-digraph G with n vertices and a one-sided convex point set S so that G does not admit a 1-bend upward point-set embedding on S.
On 1-Bend Upward Point-Set Embeddings of st-Digraphs
Di Giacomo E.;Montecchiani F.;
2024
Abstract
We study the upward point-set embeddability of digraphs on one-sided convex point sets with at most 1 bend per edge. We provide an algorithm to compute a 1-bend upward point-set embedding of outerplanar st-digraphs on arbitrary one-sided convex point sets. We complement this result by proving that for every n≥18 there exists a 2-outerplanar st-digraph G with n vertices and a one-sided convex point set S so that G does not admit a 1-bend upward point-set embedding on S.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.
