کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868496 | 1439978 | 2018 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Arc diagrams, flip distances, and Hamiltonian triangulations
ترجمه فارسی عنوان
نمودارهای قوس، فاصله تلنگر، و مثلثیل همیلتون
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
حداکثر نمودارهای مسطح نمودار فلیپ، نمودار همیلتون دکمه های کتاب، قطر نمودار،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that every triangulation (maximal planar graph) on nâ¥6 vertices can be flipped into a Hamiltonian triangulation using a sequence of less than n/2 combinatorial edge flips. The previously best upper bound uses 4-connectivity as a means to establish Hamiltonicity. But in general about 3n/5 flips are necessary to reach a 4-connected triangulation. Our result improves the upper bound on the diameter of the flip graph of combinatorial triangulations on n vertices from 5.2nâ33.6 to 5nâ23. We also show that for every triangulation on n vertices there is a simultaneous flip of less than 2n/3 edges to a 4-connected triangulation. The bound on the number of edges is tight, up to an additive constant. As another application we show that every planar graph on n vertices admits an arc diagram with less than n/2 biarcs, that is, after subdividing less than n/2 (of potentially 3nâ6) edges the resulting graph admits a 2-page book embedding.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 68, March 2018, Pages 206-225
Journal: Computational Geometry - Volume 68, March 2018, Pages 206-225
نویسندگان
Jean Cardinal, Michael Hoffmann, Vincent Kusters, Csaba D. Tóth, Manuel Wettstein,