Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649424 | Discrete Mathematics | 2009 | 14 Pages |
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
Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia,