• Title of article

    On embedding a cycle in a plane graph

  • Author/Authors

    Cortese، نويسنده , , Pier Francesco and Di Battista، نويسنده , , Giuseppe and Patrignani، نويسنده , , Maurizio and Pizzonia، نويسنده , , Maurizio، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2009
  • Pages
    14
  • From page
    1856
  • To page
    1869
  • Abstract
    Consider a planar drawing Γ 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 Γ , following the circles that correspond in Γ 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.
  • Keywords
    graph drawing , Clustered graph , Planarity testing , Clustered planarity , cycle , embedding
  • Journal title
    Discrete Mathematics
  • Serial Year
    2009
  • Journal title
    Discrete Mathematics
  • Record number

    1598657