Name
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 2^2^^^@W^^^(^^^n^^^) and on the other hand every disk graph can be realized by disks with integer coordinates and radii that are at most 2^2^^^O^^^(^^^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 Kratochvil and Matousek. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jctb.2012.09.004 | Journal of Combinatorial Theory |
Keywords | DocType | Volume |
integer realization,unit disk graph,integer grid,disk graph,analogous result,integer disk,integer radius,line segment,segment graph,radius disk,intersection graph | Journal | 103 |
Issue | ISSN | Citations |
1 | 0095-8956 | 9 |
PageRank | References | Authors |
0.53 | 25 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin McDiarmid | 1 | 1071 | 167.05 |
| Tobias Müller | 2 | 214 | 15.95 |