Consider a planar drawing Γ 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 nonintersecting closed curve inside Γ, following the circles that correspond in Γ 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. -
PIER FRANCESCO, C., DI BATTISTA, G., Patrignani, M., Pizzonia, M. (2005). On Embedding a Cycle in a Plane Graph. In Graph Drawing, GD 2005, Lecture Notes in Computer Science 3843 (pp. 49-60). BERLIN HEIDELBERG : Springer-Verlag [10.1007/11618058_5].
On Embedding a Cycle in a Plane Graph
DI BATTISTA, Giuseppe;PATRIGNANI, Maurizio;PIZZONIA, MAURIZIO
2005-01-01
Abstract
Consider a planar drawing Γ 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 nonintersecting closed curve inside Γ, following the circles that correspond in Γ 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. -I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
