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 , pp. 49-60(Official URL: http://dx.doi.org/10.1007/11618058_5).

Full text not available from this repository.


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

Actions (login required)

View Item View Item