کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414437 680938 2007 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Drawings of planar graphs with few slopes and segments
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Drawings of planar graphs with few slopes and segments
چکیده انگلیسی

We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). In a companion paper, drawings of non-planar graphs with few slopes are also considered.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 38, Issue 3, October 2007, Pages 194-212