Drawing Bipartite Graphs on Two Parallel Convex Curves - Di Giacomo, Emilio; Grilli, Luca; Liotta, Giuseppe (Journal of Graph Algorithms and Applications, 2008)
Let G be a bipartite graph, and let λe,λi be two parallel convex curves; we study the question about whether Gadmits a planar straight-line drawing such that the vertices of one partite set of G lie on λe and the vertices of theother partite set lie on λi. A characterization is presented that gives rise to linear time testing algorithm. We alsodescribe a drawing algorithm that runs in linear time if the curves are two concentric circles and the real RAM model of computationis adopted. <!---->