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

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