Back to Search Start Over

On embedding a cycle in a plane graph

Authors :
Pier Francesco Cortese
Giuseppe Di Battista
Maurizio Patrignani
Maurizio Pizzonia
p. f., Cortese
DI BATTISTA, Giuseppe
Patrignani, Maurizio
Pizzonia, Maurizio
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