Let G be a bipartite graph, and let c_e,c_i be two parallel convex curves; we study the question about whether G admits a planar straight-line drawing such that the vertices of one partite set of G lie on c_e and the vertices of the other partite set lie on c_i. A characterization is presented that gives rise to linear time testing algorithm. We also describe a drawing algorithm that runs in linear time if the curves are two concentric circles and the real RAM model of computation is adopted.
Drawing Bipartite Graphs on Two Parallel Convex Curves
DI GIACOMO, Emilio;GRILLI, LUCA;LIOTTA, Giuseppe
2008
Abstract
Let G be a bipartite graph, and let c_e,c_i be two parallel convex curves; we study the question about whether G admits a planar straight-line drawing such that the vertices of one partite set of G lie on c_e and the vertices of the other partite set lie on c_i. A characterization is presented that gives rise to linear time testing algorithm. We also describe a drawing algorithm that runs in linear time if the curves are two concentric circles and the real RAM model of computation is adopted.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.
