Let G be a degree-3 planar biconnected graph with n vertices. Let Opt(G) be the minimum number of bends in any orthogonal planar drawing of G.We show that G admits a planar orthogonal drawing D with at most Opt(G)+3 bends that can constructed in O(n 2) time. The fastest known algorithm for constructing a bend-minimum drawing of G has time-complexity O(n 5log n) and therefore, we present a significantly faster algorithm that constructs almost bend-optimal drawings.
Almost Bend-Optimal Planar Orthogonal Drawings of Biconnected Degree-3 Planar Graphs in Quadratic Time
LIOTTA, Giuseppe
1999
Abstract
Let G be a degree-3 planar biconnected graph with n vertices. Let Opt(G) be the minimum number of bends in any orthogonal planar drawing of G.We show that G admits a planar orthogonal drawing D with at most Opt(G)+3 bends that can constructed in O(n 2) time. The fastest known algorithm for constructing a bend-minimum drawing of G has time-complexity O(n 5log n) and therefore, we present a significantly faster algorithm that constructs almost bend-optimal drawings.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.
