کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653855 | 1632798 | 2012 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Connectivity augmentation in planar straight line graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
It is shown that every connected planar straight line graph with n≥3n≥3 vertices has an embedding preserving augmentation to a 2-edge connected planar straight line graph with at most ⌊(2n−2)/3⌋⌊(2n−2)/3⌋ new edges. It is also shown that every planar straight line tree with n≥3n≥3 vertices has an embedding preserving augmentation to a 2-edge connected planar topological graph with at most ⌊n/2⌋⌊n/2⌋ new edges. These bounds are the best possible. However, for every n≥3n≥3, there are planar straight line trees with nn vertices that do not have an embedding preserving augmentation to a 2-edge connected planar straight line graph with fewer than 1733n−O(1) new edges.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 33, Issue 3, April 2012, Pages 408–425
Journal: European Journal of Combinatorics - Volume 33, Issue 3, April 2012, Pages 408–425
نویسندگان
Csaba D. Tóth,