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 stripes. Consider a non-simple 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 stripes 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. -
p. f., C., DI BATTISTA, G., Patrignani, M., Pizzonia, M. (2009). On Embedding a Cycle in a Plane Graph. DISCRETE MATHEMATICS, 309(7), 1856-1869 [10.1016/j.disc.2007.12.090].
On Embedding a Cycle in a Plane Graph
DI BATTISTA, Giuseppe;PATRIGNANI, Maurizio;PIZZONIA, MAURIZIO
2009-01-01
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 stripes. Consider a non-simple 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 stripes 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.
