کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652563 | 1632599 | 2009 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On planar graphs with large tree-width and small grid minors
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given a simple planar graph with tree-width w and side size of the largest square grid minor g, it is known that g⩽w⩽5g−1. Thus, the side size of the largest grid minor is a constant approximation for the tree-width in planar graphs. In this work we analyze the lower bounds of this approximation. In particular, we present a class of planar graphs with ⌊3g/2⌋−1⩽w⩽⌊3g/2⌋. We conjecture that in the worst case w=2g+o(g). For this conjecture we have two candidate classes of planar graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 32, 15 March 2009, Pages 35-42
Journal: Electronic Notes in Discrete Mathematics - Volume 32, 15 March 2009, Pages 35-42