کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656935 1343701 2013 30 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Integer realizations of disk and segment graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Integer realizations of disk and segment graphs
چکیده انگلیسی

A disk graph is the intersection graph of disks in the plane, a unit disk graph is the intersection graph of same radius disks in the plane, and a segment graph is an intersection graph of line segments in the plane. Every disk graph can be realized by disks with centers on the integer grid and with integer radii; and similarly every unit disk graph can be realized by disks with centers on the integer grid and equal (integer) radius; and every segment graph can be realized by segments whose endpoints lie on the integer grid. Here we show that there exist disk graphs on n vertices such that in every realization by integer disks at least one coordinate or radius is 22Ω(n) and on the other hand every disk graph can be realized by disks with integer coordinates and radii that are at most 22O(n); and we show the analogous results for unit disk graphs and segment graphs. For (unit) disk graphs this answers a question of Spinrad, and for segment graphs this improves over a previous result by Kratochvíl and Matoušek.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 103, Issue 1, January 2013, Pages 114-143