کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414729 681016 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Outerplanar graph drawings with few slopes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Outerplanar graph drawings with few slopes
چکیده انگلیسی

We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that Δ−1Δ−1 edge slopes suffice for every outerplanar graph with maximum degree Δ⩾4Δ⩾4. This improves on the previous bound of O(Δ5)O(Δ5), which was shown for planar partial 3-trees, a superclass of outerplanar graphs. The bound is tight: for every Δ⩾4Δ⩾4 there is an outerplanar graph with maximum degree Δ   that requires at least Δ−1Δ−1 distinct edge slopes in an outerplanar straight-line drawing.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 5, July 2014, Pages 614–624
نویسندگان
, , ,