Lattice embeddings of trees

DOI10.1016/J.EJC.2008.09.016MaRDI QIDQ1024313zbMATH OpenOpenAlexFDO

Authors Wilfried Imrich, Matjaž Kovše

Publication date 17 June 2009

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2008.09.016

zbMATH Keywords

distance preservingisometric embeddingtree

Mathematics Subject Classification ID

Trees (05C05) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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.

Recommendations

• On the dimension of trees
• The lattice dimension of a graph
• Low-Distortion Embeddings of Trees
• scientific article; zbMATH DE number 4031713
• scientific article; zbMATH DE number 2084288

Cites work

• Distance-preserving subgraphs of hypercubes
• Embeddability of the combinohedron
• Embedding into rectilinear spaces
• scientific article; zbMATH DE number 3585454 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 2170442 (Why is no real title available?)
• scientific article; zbMATH DE number 2108391 (Why is no real title available?)
• scientific article; zbMATH DE number 802815 (Why is no real title available?)
• Media theory. Interdisciplinary applied mathematics.
• On semicube graphs
• The lattice dimension of a graph
• The lattice dimension of benzenoid systems

Cited in

(14)

• Embeddings of binary trees in lines
• Embedding meshes of trees into deBruijn graphs
• Bipartite embeddings of trees in the plane
• The fiber dimension of a graph
• Vector lattices and rooted trees
• Embedding trees in recursive circulants
• Grid straight-line embeddings of trees with a minimum number of bends per path
• A lattice on decreasing trees: the metasylvester lattice
• Perfect trees and elementary embeddings
• scientific article; zbMATH DE number 4031713 (Why is no real title available?)
• A linear time algorithm for embedding Christmas trees into certain trees
• scientific article; zbMATH DE number 1406265 (Why is no real title available?)
• Historical lattice trees
• A poset-based approach to embedding median graphs in hypercubes and lattices

This page was built for publication: Lattice embeddings of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024313)