کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420598 683957 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Convex drawings of graphs with non-convex boundary constraints
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Convex drawings of graphs with non-convex boundary constraints
چکیده انگلیسی

In this paper, we study a new problem of convex drawing of planar graphs with non-convex boundary constraints, and call a drawing in which every inner-facial cycle is drawn as a convex polygon an inner-convex drawing. It is proved that every triconnected plane graph with the boundary fixed with a star-shaped polygon whose kernel has a positive area admits an inner-convex drawing. We also prove that every four-connected plane graph whose boundary is fixed with a crown-shaped polygon admits an inner-convex drawing. We present linear time algorithms to construct inner-convex drawings for both cases.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 12, 28 June 2008, Pages 2368–2380
نویسندگان
, ,