کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
415167 681187 2016 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Thickness and colorability of geometric graphs
ترجمه فارسی عنوان
ضخامت و رنگ پذیری نمودارهای هندسی ☆
کلمات کلیدی
نمودار کامل؛ ضخامت هندسی؛ رنگ آمیزی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

The geometric thickness of a graph G is the smallest integer t such that there exist a straight-line drawing Γ of G and a partition of its straight-line edges into t subsets, where each subset induces a planar drawing in Γ. Over a decade ago, Hutchinson, Shermer, and Vince proved that any n  -vertex graph with geometric thickness two can have at most 6n−186n−18 edges, and for every n≥8n≥8 they constructed a geometric thickness-two graph with 6n−206n−20 edges. In this paper, we construct geometric thickness-two graphs with 6n−196n−19 edges for every n≥9n≥9, which improves the previously known 6n−206n−20 lower bound. We then construct a thickness-two graph with 10 vertices that has geometric thickness three, and prove that the problem of recognizing geometric thickness-two graphs is NP-hard, answering two questions posed by Dillencourt, Eppstein and Hirschberg. Finally, we prove the NP-hardness of coloring graphs of geometric thickness t   with 4t−14t−1 colors, which strengthens a result of McGrae and Zito, when t=2t=2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 56, July 2016, Pages 1–18
نویسندگان
, , ,