Good quality virtual realization of unit disk graphs

We consider the problem of finding a realization of an n-vertex <em>unit disk graph</em> (UDG) expressed in <em>general form</em>, 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 <em>quality</em> of the realization. Thus, an optimum quality realization has quality between 1/2 and 1. Kuhn et al. gave a<em>O</em>(log^3.5 <em>n</em> (loglog <em>n</em>)^1/2}) quality realization that requires solving a linear program with exponentially many constraints by using the <em>ellipsoid </em>algorithm. <p>In this article, we give a <em>combinatorial </em>algorithm that achieves an <em>O</em>(log³ <em>n</em>) quality realization of an <em>n</em>-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 <em>minimum clique partition problem</em> 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.</p>

Abstract licence: CC BY

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.