کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414663 680999 2015 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cubic plane graphs on a given point set
ترجمه فارسی عنوان
نمودار هواپیما مکعب بر روی یک مجموعه نقطه داده شده
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let P   be a set of n≥4n≥4 points in the plane that is in general position and such that n is even. We investigate the problem whether there is a (0-, 1- or 2-connected) cubic plane straight-line graph on P. No polynomial-time algorithm is known for this problem. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P  , we give the first polynomial-time algorithm that checks for 2-connected cubic plane graphs; the algorithm is constructive and runs in time O(n3)O(n3). We also show which graph structure can be expected when there is a cubic plane graph on P; e. g., a cubic plane graph on P implies a connected cubic plane graph on P, and a 2-connected cubic plane graph on P implies a 2-connected cubic plane graph on P that contains the boundary cycle of P  . We extend the above algorithm to check for arbitrary cubic plane graphs in time O(n3)O(n3).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 1, January 2015, Pages 1–13
نویسندگان
, ,