2009.03.11 | Bjarke Hammersholt Roune

There is coffee and cake at this seminar.

Abstract: Given a set P of n points in d-dimensional space, a unit-disk graph is a graph built with P as the vertex set, by connecting two vertices (i.e., points) if and only if their Euclidean distance is at most one. We are interested in problems related to the maximum cliques in a unit-diskgraph.

These graphs have numerous applications (for instance, they can be used to model wireless networks) and are well studied in computational geometry literature and other fields.

In this talk, after a brief introduction, we will survey a few previous results on this problem. First, we will review how the algorithmic problem of computing the maximum clique corresponds to the following non-algorithmic covering problem: for R^d, find the minimum value of k and a set S of k objects of diameter one, such that *any* shape of diameter one can be covered using k elements of S.

For d=2 the answer is two; for d=3 the best result sofar is five and no non-trivial result is known for higher dimensions.

We will also examine a related problem of embedding graphs as unit-disk graphs including some embeddingresults.

References

* Finding k points with minimum diameter and related problems Alok Aggarwal and HiroshiImai and Naoki Katoh and Subhash Suri, Journal of Algorithms, volume 12, pages: 38 - 56, 1991
* Approximation algorithms for maximum cliques in 3D unit-disk graphs, Peyman Afshani and Timothy Chan, CCCG, pages 6--9, 2005
* Approximation and inapproximability results for maximum clique of disc graphs in high dimensions, Peyman Afshani and Hamed Hatami, Information Processing Letters, volume 105, pages 83--87, January 2008
* On finding a large number of 3D points with a small diameter, Minghui Jiang, Discrete Applied Mathematics, 155:2355-2361, 2007

See www.daimi.au.dk/~bjarke/compmath/ for more information.