کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431044 688259 2011 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Contracting planar graphs to contractions of triangulations
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Contracting planar graphs to contractions of triangulations
چکیده انگلیسی

For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H  . We identify a class of graphs CC such that for every fixed H∈CH∈C, there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H  . The class CC is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H∈CH∈C if and only if there exists a constant cHcH such that if the treewidth of a graph is at least cHcH, it contains H   as a contraction. We also provide a characterization of CC in terms of minimal forbidden contractions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 9, Issue 3, September 2011, Pages 299–306
نویسندگان
, , ,