Drawing Bipartite Graphs on Two Curves

Di Giacomo, Emilio and Grilli, Luca and Liotta, Giuseppe (2007) Drawing Bipartite Graphs on Two Curves. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 380-385 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_36).

Full text not available from this repository.

Abstract

Let G be a bipartite graph, and let $\lambda_e,\lambda_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 $\lambda_e$ and the vertices of the other partite set lie on $\lambda_i$. A characterization is presented that gives rise to linear time testing and drawing algorithms.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_36
Classifications:P Styles > P.300 Curved
ID Code:793

Repository Staff Only: item control page

References

C. Bachmaier, F. J. Brandenburg, and M. Forster. Radial level planarity testing and embedding in linear time. J. Graph Algorithms Appl., 9(1):53-97, 2005.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

E. Di Giacomo, W. Didimo, G. Liotta, and S. K. Wismath. Curve-constrained drawings of planar graphs. Comput. Geom.: Theory and Appl., 30:1-23, 2005.

P. Eades, B. D. McKay, and N. C. Wormald. On an edge crossing problem. In Proc 9th Austr. Comp. Sci. conf., pages 327-334. Australian National University, 1986.

P. Eades and S. H. Whitesides. Drawing graphs in two layers. Theoretical Computer Science, 131(2):361-374, 1994.

F. Harary and A. Schwenk. A new crossing number for bipartite graphs. Utilitas Mathematica, 1:203-209, 1972.

M. Kaufmann and D. Wagner, editors. Drawing Graphs, volume 2025 of Lecture Notes in Computer Science. Springer-Verlag, 2001.

N. Tomii, Y. Kambayashi, and S. Yajima. On planarization algorithms of 2-level graphs. Technical Report EC77-38, Inst. of Elect. and Comm. Eng. Japan, 1977.