کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421237 | 684163 | 2012 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on planar graphs with large width parameters and small grid-minors
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given a graph GG with tree-width ω(G)ω(G), branch-width β(G)β(G), and side size of the largest square grid-minor θ(G)θ(G), it is known that θ(G)≤β(G)≤ω(G)+1≤32β(G). In this paper, we introduce another approach to bound the side size of the largest square grid-minor specifically for planar graphs. The approach is based on measuring the distances between the faces in an embedding of a planar graph. We analyze the tightness of all derived bounds. In particular, we present a class of planar graphs where θ(G)=β(G)<ω(G)=⌊32θ(G)⌋−1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issues 7–8, May 2012, Pages 1262–1269
Journal: Discrete Applied Mathematics - Volume 160, Issues 7–8, May 2012, Pages 1262–1269
نویسندگان
Alexander Grigoriev, Bert Marchal, Natalya Usotskaya, Ioan Todinca,