Logo

Login | Create Account

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. [Conference Paper]

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
Classifications:P Styles > P.999 Others
ID Code:837
Deposited By:GDEA, Administration
Deposited On:24 Jun 2008
Last Modified:18 Sep 2008 13:09
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=4875&spage=183

Repository Staff Only: item control page

References

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

2. 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).

3. 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.

4. 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.

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

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

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

15. 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.

16. 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.

17. 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.

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

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.