On meshy trees

Abstract

A graph is termed d-meshy if it can be isomorphicaly embedded in the universal d-dimensional mesh (grid) M _d . We investigate the d-meshiness of tree graphs, especially for d = 2. Trees of minimum order that are nonmeshy are identified. It is shown that for any d and n≧2, there exists an h such that the full n-ary tree of height h is not d-meshy. Spreading mesh embeddings of trees that preserve distance from the root are discussed, qs well as the characterization of meshy trees by their degree sequences.

Keywords:

• Embedding methods
• graph theory
• meshes
• trees
• VLSI layout

C.R. Categories:

• G.2.2