On Embedding a Cycle in a Plane Graph

Cortese, Pier Francesco and Di Battista, Giuseppe and Patrignani, Maurizio and Pizzonia, Maurizio (2006) On Embedding a Cycle in a Plane Graph. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 49-60 (Official URL: http://dx.doi.org/10.1007/11618058_5).

Full text not available from this repository.

Abstract

Consider a planar drawing Gamma of a planar graph G such that the vertices are drawn as small circles and the edges are drawn as thin strips. Consider a cycle c of G. Is it possible to draw c as a non-intersecting closed curve inside Gamma, following the circles that correspond in Gamma to the vertices of c and the strips that connect them? We show that this test can be done in polynomial time and study this problem in the framework of clustered planarity for highly non-connected clustered graphs.

Item Type:Conference Paper
Additional Information:10.1007/11618058_5
Classifications:P Styles > P.180 Cluster
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:679

Repository Staff Only: item control page

References

T. C. Biedl.: Drawing planar partitions III: Two constrained embedding problems. Tech. Report RRR 13-98, RUTCOR Rutgen University, 1998.

T. C. Biedl, M. Kaufmann, and P. Mutzel.: Drawing planar partitions II: HH-Drawings. Workshop on Graph-Theoretic Concepts in Computer Science (WG'98), volume 1517, pages 124--136. Springer-Verlag, 1998.

S. Cornelsen and D. Wagner.: Completely connected clustered graphs. Proc. 29th Intl. Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003), volume 2880 of LNCS, pages 168--179.Springer-Verlag, 2003.

P. F. Cortese and G. Di Battista.: Clustered planarity.

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry, pages 32--34, New York, NY, USA, 2005. ACM Press.

P. F. Cortese, G. Di Battista, M. Patrignani, and M. Pizzonia.: Clustering cycles into cycles of clusters. J. Pach, editor, Proc. Graph Drawing 2004 (GD'04), volume 3383 of LNCS, pages 100--110. Springer-Verlag, 2004.

E.Dahlhaus.: Linear time algorithm to recognize clustered planar graphs and its parallelization. C.L. Lucchesi, editor, LATIN '98, 3rd Latin American symposium on theoretical informatics, Campinas, Brazil, April 20--24, 1998, volume 1380 of LNCS, pages 239--248, 1998.

G. Di Battista, W. Didimo, and A. Marcandalli.: Planarization of clustered graphs. Proc. Graph Drawing 2001 (GD'01), LNCS, pages 60--74. Springer-Verlag, 2001.

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

S. Even.: Graph Algorithms. Computer Science Press, Potomac, Maryland, 1979.

Q. W. Feng, R. F. Cohen, and P. Eades.: How to draw a planar clustered graph. Ding-Zhu Du and Ming Li, editors, Proc. COCOON'95, volume 959 of LNCS, pages 21--30. Springer-Verlag, 1995.

Q. W. Feng, R. F. Cohen, and P. Eades.: Planarity for clustered graphs. P. Spirakis, editor, Symposium on Algorithms (Proc. ESA'95), volume 979 of LNCS, pages 213--226. Springer-Verlag, 1995.

C.Gutwenger, M.Jünger, S. Leipert, P. Mutzel, M. Percan, and Rene Weiskircher.: Advances in C-planarity testing of clustered graphs. Stephen G. Kobourov and Michael T. Goodrich, editors, Graph Drawing 2002 (GD'02), volume 2528 of LNCS, pages 220--235. Springer-Verlag, 2002.

T. Lengauer.: Hierarchical planarity testing algorithms. J. ACM, 36(3):474--509, 1989.