On Embedding a Cycle in a Plane Graph

摘要

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 non-intersecting 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.