Lattice embeddings of trees (Q1024313)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Lattice embeddings of trees |
scientific article; zbMATH DE number 5565560
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Lattice embeddings of trees |
scientific article; zbMATH DE number 5565560 |
Statements
Lattice embeddings of trees (English)
0 references
17 June 2009
0 references
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.
0 references
isometric embedding
0 references
distance preserving
0 references
tree
0 references
