On Embedding a Cycle in a Plane GraphCortese, Pier Francesco and Di Battista, Giuseppe and Patrignani, Maurizio and Pizzonia, Maurizio (2006) On Embedding a Cycle in a Plane Graph. In: Graph Drawing 13th International Symposium, GD 2005, September 1214, 2005 , pp. 4960(Official URL: http://dx.doi.org/10.1007/11618058_5). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/11618058_5
AbstractConsider 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 strips. Consider a cycle c of G. Is it possible to draw c as a nonintersecting closed curve inside Gamma, following the circles that correspond in Gamma to the vertices of c and the strips 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 nonconnected clustered graphs.
Actions (login required)
