کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418688 681709 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the bend-number of planar and outerplanar graphs
ترجمه فارسی عنوان
بر تعداد خمیدگی نمودارهای فلاری و بیرونی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

The bend-number  b(G)b(G) of a graph GG is the minimum kk such that GG may be represented as the edge intersection graph of a set of grid paths with at most kk bends. We confirm a conjecture of Biedl and Stern showing that the maximum bend-number of outerplanar graphs is 2. Moreover we improve the formerly known lower and upper bounds for the maximum bend-number of planar graphs from 2 and 5 to 3 and 4, respectively.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 179, 31 December 2014, Pages 109–119
نویسندگان
, , ,