کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438169 690234 2014 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
2-Connecting outerplanar graphs without blowing up the pathwidth
ترجمه فارسی عنوان
2 - اتصال نمودار های بیرونی بدون انفجار عرض مسیر
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G  , which is 2-vertex-connected, outerplanar and of pathwidth O(p)O(p). This settles an open problem raised by Biedl [1], in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two-dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl [1] for 2-vertex-connected outerplanar graphs will work for all outer planar graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 554, 16 October 2014, Pages 119–134
نویسندگان
, , , ,