کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414683 681004 2014 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Reprint of: Grid representations and the chromatic number
ترجمه فارسی عنوان
چاپ مجدد: نمایندگی گرید و شماره رنگی
کلمات کلیدی
نقشه های نمودار، توری، رنگ آمیزی نمودار، شماره کروماتیک
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A grid drawing of a graph maps vertices to the grid ZdZd and edges to line segments that avoid grid points representing other vertices. We show that a graph G   is qdqd-colorable, d  , q⩾2q⩾2, if and only if there is a grid drawing of G   in ZdZd in which no line segment intersects more than q   grid points. This strengthens the result of D. Flores Pen̋aloza and F.J. Zaragoza Martinez. Second, we study grid drawings with a bounded number of columns, introducing some new NPNP-complete problems. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures asked by D. Flores Pen̋aloza and F.J. Zaragoza Martinez.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 3, Part B, April 2014, Pages 480–492
نویسندگان
,