کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414240 | 680855 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Making triangulations 4-connected using flips
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We show that any combinatorial triangulation on n vertices can be transformed into a 4-connected one using at most ⌊(3n−9)/5⌋⌊(3n−9)/5⌋ edge flips. We also give an example of an infinite family of triangulations that requires this many flips to be made 4-connected, showing that our bound is tight. In addition, for n⩾19n⩾19, we improve the upper bound on the number of flips required to transform any 4-connected triangulation into the canonical triangulation (the triangulation with two dominant vertices), matching the known lower bound of 2n−152n−15. Our results imply a new upper bound on the diameter of the flip graph of 5.2n−33.65.2n−33.6, improving on the previous best known bound of 6n−306n−30.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 2, Part A, February 2014, Pages 187–197
Journal: Computational Geometry - Volume 47, Issue 2, Part A, February 2014, Pages 187–197
نویسندگان
Prosenjit Bose, Dana Jansens, André van Renssen, Maria Saumell, Sander Verdonschot,