Logo

Login | Create Account

Simultaneous Graph Embedding with Bends and Circular Arcs

Cappos, Justin and Estrella-Balderrama, Alejandro and Fowler, J. Joseph and Kobourov, Stephen G. (2007) Simultaneous Graph Embedding with Bends and Circular Arcs. [Conference Paper]

Full text not available from this repository.

Abstract

We consider the problem of simultaneous embedding of planar graphs. We demonstrate how to simultaneously embed a path and an n-level planar graph and how to use radial embeddings for curvilinear simultaneous embeddings of a path and an outerplanar graph. We also show how to use star-shaped levels to find 2-bends per path edge simultaneous embeddings of a path and an outerplanar graph. All embedding algorithms run in O(n) time.

Item Type:Conference Paper
Classifications:M Methods > M.999 Others
P Styles > P.999 Others
P Styles > P.660 Radial
ID Code:765
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.

P. Bose. On embedding an outer-planar graph in a point set. CGTA: Computational Geometry: Theory and Applications, 23(3):303-312, 2002.

P. Brass, E. Cenek, C. A. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. G. Kobourov, A. Lubiw, and J. S. B. Mitchell. On simultaneous graph embedding. In 8th

Workshop on Algorithms and Data Structures, pages 243-255, 2003.

J. Cappos, A. Estrella-Balderrama, J. J. Fowler, and S. G. Kobourov. Simultaneous graph embedding with bends and circular arcs. Technical Report TR06-02, University of Arizona, 2006.

G. Di Battista and E. Nardelli. Hierarchies and planarity theory. IEEE Trans. Systems Man Cybernet., 18(6):1035-1046 (1989), 1988.

P. Eades, Q. Feng, X. Lin, and H. Nagamochi. Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Algorithmica, 44(1):1-32, 2006.

C. Erten and S. G. Kobourov. Simultaneous embedding of planar graphs with few bends. In 12th Symposium on Graph Drawing (GD), pages 195-205, 2004.

A. Estrella-Balderrama, J. J. Fowler, and S. G. Kobourov. Characterization of unlabeled level planar trees. Manuscript accepted by 14th Symposium on Graph Drawing, 2006.

S. Felsner, G. Liotta, and S. Wismath. Straight-line drawings on restricted integer grids in two and three dimensions. Journal of Graph Algorithms and Applications, 7(4):363-398, 2003.

M. Geyer, M. Kaufmann, and I. Vrto. Two trees which are self-intersecting when drawn simultaneously. In 13th Symposium on Graph Drawing, pages 201-210, 2005.

M. Junger and S. Leipert. Level planar embedding in linear time. J. Graph Algorithms Appl., 6(1):67-113, 2002.

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.