Article ID Journal Published Year Pages File Type
4649424 Discrete Mathematics 2009 14 Pages PDF
Abstract

Consider a planar drawing ΓΓ of a planar graph GG such that the vertices are drawn as small circles and the edges are drawn as thin stripes. Consider a non-simple cycle cc of GG. Is it possible to draw cc as a non-intersecting closed curve inside ΓΓ, following the circles that correspond in ΓΓ to the vertices of cc 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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,