Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces

Di Battista, Giuseppe and Frati, Fabrizio (2008) Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 291-302 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_29).

Full text not available from this repository.

Abstract

Let C be a clustered graph and suppose that the planar embedding of its underlying graph is fixed. Is testing the c-planarity of $C$ easier than in the variable embedding setting? In this paper we give a first contribution towards answering the above question. Namely, we characterize c-planar embedded flat clustered graphs with at most five vertices per face and give an efficient testing algorithm for such graphs. The results are based on a more general methodology that shades new light on the c-planarity testing problem.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_29
Classifications:G Algorithms and Complexity > G.350 Clusters
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:846

Repository Staff Only: item control page

References

S. Cornelsen and D. Wagner. Completely connected clustered graphs. Journal of Discrete Algorithms, 4(2):313-323, 2006.

P. F. Cortese and G. Di Battista. Clustered planarity. In ACM SoCG 05, pages 32-34, 2005.

P. F. Cortese, G. Di Battista, M. Patrignani, and M. Pizzonia. Clustering cycles into cycles of clusters. Journal of Graph Algorithms and Applications, 9(3):391-413, 2005

P. F. Cortese, G. Di Battista, M. Patrignani, and M. Pizzonia. On embedding a cycle in a plane graph. In GD 05, pages 49-60, 2005.

E. Dahlhaus. A linear time algorithm to recognize clustered graphs and its parallelization. In Proc. LATIN, pages 239-248, 1998.

G. Di Battista and F. Frati. Efficient c-planarity testing for embedded flat clustered graphs with small faces. Tech. Report RT-DIA-119-2007, Dip. Inf. e Aut., Univ. Roma Tre, 2007.

Q. Feng, R. F. Cohen, and P. Eades. Planarity for clustered graphs. In ESA, pages 213-226, 1995.

M. T. Goodrich, G. S. Lueker, and J. Z. Sun. C-planarity of extrovert clustered graphs. In GD 05, pages 211-222, 2005.

C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, and R. Weiskircher. Advances in c-planarity testing of clustered graphs. In GD 02, pages 220-235, 2002.

D. G. Kirkpatrick. Establishing order in planar subdivisions. Discrete & Computational Geometry, 3:267-280, 1988.

T. Nishizeki and N. Chiba. Planar Graphs: Theory and Algorithms. North-Holland, 1988.