کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414683 | 681004 | 2014 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reprint of: Grid representations and the chromatic number
ترجمه فارسی عنوان
چاپ مجدد: نمایندگی گرید و شماره رنگی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نقشه های نمودار، توری، رنگ آمیزی نمودار، شماره کروماتیک
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Computational Geometry - Volume 47, Issue 3, Part B, April 2014, Pages 480–492
نویسندگان
Martin Balko,