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

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
نویسندگان
,