Abstract
Every graph G can be represented by a collection of equi-radii spheres in a d-dimensional metric \Delta such that there is an edge uv in G if and only if the spheres corresponding to u and v intersect. The smallest integer d such that G can be represented by a collection of spheres (all of the same radius) in \Delta is called the sphericity of G, and if the collection of spheres are nonoverlapping, then the value d is called the contact-dimension of G. In this paper, we study the sphericity and contact-dimension of the complete bipartite graph Kn,n in various Lp-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems.