کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649424 1342454 2009 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On embedding a cycle in a plane graph
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On embedding a cycle in a plane graph
چکیده انگلیسی

Consider a planar drawing ΓΓ of a planar graph GG such that the vertices are drawn as small circles and the edges are drawn as thin stripes. Consider a non-simple cycle cc of GG. Is it possible to draw cc as a non-intersecting closed curve inside ΓΓ, following the circles that correspond in ΓΓ to the vertices of cc 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 7, 8 April 2009, Pages 1856–1869
نویسندگان
, , , ,