Matched Drawings of Planar Graphs

Di Giacomo, Emilio and Didimo, Walter and Van Kreveld, Marc and Liotta, Giuseppe and Speckmann, Bettina (2008) Matched Drawings of Planar Graphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 183-194 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_19).

Full text not available from this repository.

Abstract

A natural way to draw two planar graphs whose vertex sets are matched is to assign each matched pair a unique y-coordinate. In this paper we introduce the concept of such matched drawings, which are a relaxation of simultaneous geometric embeddings with mapping. We study which classes of graphs allow matched drawings and show that (i) two 3-connected planar graphs or a 3-connected planar graph and a tree may not be matched drawable, while (ii) two trees or a planar graph and a planar graph of some special families-such as unlabeled level planar (ULP) graphs or the family of "carousel graphs"-are always matched drawable.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_19
Classifications:P Styles > P.720 Straight-line
G Algorithms and Complexity > G.490 Embeddings
ID Code:837

Repository Staff Only: item control page

References

U. Brandes and T. Erlebach, editors. Network Analysis, volume 3418 of LNCS. Springer, 2005.

U. Brandes, C. Erten, J. Fowler, F. Frati, M. Geyer, C. Gutwenger, S.-H. Hong, M. Kaufmann, S. Kobourov, G. Liotta, P. Mutzel, and A. Symvonis. Colored simultaneous geometric embeddings. In Proc. 13th Annual Intern. Computing and Combinatorics Conference, LNCS, 2007 (to appear).

P. Braß, E. Cenek, C. A. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. G. Kobourov, A. Lubiw, and J. S. B. Mitchell. On simultaneous planar graph embeddings. Computational Geometry: Theory and Applications, 36(2):117-130, 2007.

J. Cappos, A. Estrella-Balderrama, J. J. Fowler, and S. G. Kobourov. Simultaneous graph embedding with bends and circular arcs. In Proc. 14th Intern. Symp. on Graph Drawing, volume 4372 of LNCS, pages 95-107, Springer, 2006.

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.

C. Demetrescu, G. Di Battista, I. Finocchi, G. Liotta, M. Patrignani, and M. Pizzonia. Infinite trees and the future. In Proc. 7th Intern. Symp. on Graph Drawing, volume 1731 of LNCS, pages 379-391, Springer, 1999.

E. Di Giacomo, W. Didimo, L. Grilli, and G. Liotta. Graph visualization techniques for web clustering engines. IEEE Transactions on Visualization and Computer Graphics, 13(2):294-304, 2007.

E. Di Giacomo and G. Liotta. Simultaneous embedding of outerplanar graphs, paths, and cycles. International Journal of Computational Geometry and Applications, 17(2):139-160, 2007.

C. Erten and S. G. Kobourov. Simultaneous embedding of planar graphs with few bends. Journal of Graph Algorithms and Applications, 9(3):347-364, 2005.

A. Estrella-Balderrama, J. J. Fowler, and S. G. Kobourov. Characterization of unlabeled level planar trees. In Proc. 14th Intern. Symp. on Graph Drawing, volume 4372 of LNCS, pages 367-379, Springer, 2007.

H. Fernau, M. Kaufmann, and M. Poths. Comparing trees via crossing minimization. In Proc. 25th Conf. on Foundations of Software Technology and Theoretical Computer Science, pages 457-469, 2005.

J. J. Fowler and S. G. Kouborov. Characterization of unlabeled level planar graphs. Technical Report TR06-04, Dep. of Computer Science, University of Arizona, 2006.

F. Frati. Embedding graphs simultaneously with fixed edges. In Proc. 14th Intern. Symp. on Graph Drawing, volume 4372 of LNCS, pages 108-113, Springer, 2006.

C. Friedrich and P. Eades. Graph drawing in motion. Journal of Graph Algorithms and Applications, 6(3):353-370, 2002.

M. Geyer, M. Kaufmann, and I. Vrt'o. Two trees which are self-intersecting when drawn simultaneously. In Proc. 13th Intern. Symp. on Graph Drawing, volume 3843 of LNCS pages 201-210, Springer 2005.

M. L. Huang, P. Eades, and R. F. Cohen. WebOFDAV-navigating and visualising the web online with animated context swapping. Computer Networks and ISDN Systems, 30:638-642, 1998.

K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout adjustment and the mental map. Journal of Visual Languages and Computing, 6(2):183-210, 1995.

S. North. Incremental layout in dynadag. In Proc. 3rd Intern. Symp. on Graph Drawing, volume 1027 of LNCS, pages 409-418, Springer, 1995.