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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/846

Actions (login required)

View Item View Item