Back to Search
Start Over
On embedding a cycle in a plane graph
- Source :
- Discrete Mathematics. (7):1856-1869
- Publisher :
- Elsevier B.V.
-
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.
Details
- Language :
- English
- ISSN :
- 0012365X
- Issue :
- 7
- Database :
- OpenAIRE
- Journal :
- Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....1a1298a720cad65db9fd388528159c3d
- Full Text :
- https://doi.org/10.1016/j.disc.2007.12.090