کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414729 | 681016 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Outerplanar graph drawings with few slopes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Outerplanar graph drawings with few slopes Outerplanar graph drawings with few slopes](/preview/png/414729.png)
چکیده انگلیسی
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
Journal: Computational Geometry - Volume 47, Issue 5, July 2014, Pages 614–624
نویسندگان
Kolja Knauer, Piotr Micek, Bartosz Walczak,