Logo

Login | Create Account

Drawing Bipartite Graphs on Two Curves

Di Giacomo, Emilio and Grilli, Luca and Liotta, Giuseppe (2007) Drawing Bipartite Graphs on Two Curves. [Conference Paper]

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
Classifications:P Styles > P.300 Curved
ID Code:793
Deposited By:GDEA, Administration
Deposited On:04 May 2007
Last Modified:18 Sep 2008 13:09
Alternative Locations:http://www.springer.com/dal/home/computer/lncs?SGWID=1-164-22-173721109-0

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.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.