Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 114-143 |
Number of pages | 30 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 103 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2013 |