### Good quality virtual realization of unit disk graphs

#### Abstract

We consider the problem of finding a realization of an n-vertex

*unit disk graph*(UDG) expressed in*general form*, say, as an adjacency matrix. The problem is to construct an embedding of the graph in low-dimensional Euclidean space so that the ratio of the length of the longest edge under the embedding to the length of the shortest non-edge under the embedding is as small as possible; the measure is known as the*quality*of the realization. Thus, an optimum quality realization has quality between 1/2 and 1. Kuhn et al. gave a*O*(log^{3.5}*n*(loglog*n*)^{1/2}}) quality realization that requires solving a linear program with exponentially many constraints by using the*ellipsoid*algorithm.In this article, we give a *combinatorial *algorithm that achieves an *O*(log^{3} *n*) quality realization of an *n*-vertex UDG expressed in general form. Thus, not only is our algorithm an improvement, it also bypasses the standard and costly technique of solving a linear program with exponentially many “spreading constraints.” As a side effect of our construction, we get the first constant-factor approximation to the *minimum clique partition problem* for UDGs expressed in general form. Such a clique partition also represents our key technical contribution. If the embedding is allowed to reside in higher dimensional space, we obtain improved results: a quality-2 embedding in constant dimensional Euclidean space.

#### Full Text:

PDFDOI: http://dx.doi.org/10.20382/jocg.v2i1a5

ISSN: 1920-180X