1. On embedding a cycle in a plane graph
- Author
-
Cortese, Pier Francesco, Di Battista, Giuseppe, Patrignani, Maurizio, and Pizzonia, Maurizio
- Subjects
- *
EMBEDDINGS (Mathematics) , *GRAPH theory , *PATHS & cycles in graph theory , *GEOMETRICAL drawing , *CIRCLE , *POLYNOMIALS , *MATHEMATICAL analysis - Abstract
Abstract: Consider a planar drawing of a planar graph such that the vertices are drawn as small circles and the edges are drawn as thin stripes. Consider a non-simple cycle of . Is it possible to draw as a non-intersecting closed curve inside , following the circles that correspond in to the vertices of 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. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF