Faster isometric embedding in products of complete graphs

F. Aurenhammer, M. Formann, R. Idury, A. Schaeffer, and F. Wagner

Abstract:

An isometric embedding of a connected graph $G$ into a cartesian product of complete graphs is equivalent to a labeling of each vertex of $G$ by a string of fixed length such that the distance in $G$ between two vertices is equal to the Hamming distance between their labels. We give a simple $O(D(m,n)+n^{2})$-time algorithm for deciding if $G$ admits such an embedding, and for labeling $G$ if one exists, where $D(m,n)$ is the time needed to compute the all-pairs distance matrix of a graph with $m$ edges and $n$ vertices. If the distance matrix is part of the input, our algorithm runs in $O(n^{2})$ time. We also show that an $n$-vertex subgraph of $(K_{a})^{d}$, the cartesian product of $d$ equal-sized complete graphs, cannot have more than $\frac{a-1}{2}n\log_a n$ edges. With this result our algorithm can be used to decide whether a graph $G$ is an $a$-ary Hamming graph in $O(n^2\log n)$ time (for fixed $a$).

Reference: F. Aurenhammer, M. Formann, R. Idury, A. Schaeffer, and F. Wagner. Faster isometric embedding in products of complete graphs. Discrete Applied Mathematics, 52:17-28, 1994. [Report B-90-06, FU Berlin, Germany, 1990].