کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10327396 | 681023 | 2013 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Grid representations and the chromatic number
ترجمه فارسی عنوان
نمایندگی شبکه و تعداد رنگی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نقشه های نمودار، توری، رنگ آمیزی نمودار، شماره کروماتیک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A grid drawing of a graph maps vertices to the grid Zd and edges to line segments that avoid grid points representing other vertices. We show that a graph G is qd-colorable, d, q⩾2, if and only if there is a grid drawing of G in Zd 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 NP-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 46, Issue 8, October 2013, Pages 990-1002
Journal: Computational Geometry - Volume 46, Issue 8, October 2013, Pages 990-1002
نویسندگان
Martin Balko,