The lattice dimension of a graph
arXiv:cs/0402028 · doi:10.1016/j.ejc.2004.05.001
Abstract
We describe a polynomial time algorithm for, given an undirected graph G, finding the minimum dimension d such that G may be isometrically embedded into the d-dimensional integer lattice Z^d.
6 pages, 3 figures