Lattice embeddings of trees (Q1024313): Difference between revisions

The lattice dimension of a graph \(G\) is the smallest \(d\) such that \(G\) embeds isometrically into the \(d\)-dimensional integer lattice \(\mathbb{Z}^d\) [see, e.g., \textit{D. Eppstein}, ``The lattice dimension of a graph,'' Eur. J. Comb. 26, No.\,5, 585--592 (2005; Zbl 1060.05072)]. This paper presents an algorithmic approach to such an embedding of a tree \(T\) on \(n\) vertices. The authors show that \(T\) can be embedded in \(O(n)\) time and coordinated in \(O(nd)\) time.