Lattice embeddings of trees (Q1024313): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
m rollbackEdits.php mass rollback Tag: Rollback |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/j.ejc.2008.09.016 / rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2084047905 / rank | |||
Revision as of 04:46, 20 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Lattice embeddings of trees |
scientific article |
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
