Embedding ternary trees in VLSI arrays (Q1099135)

Two modular schemes for embedding complete ternary trees in VLSI arrays are described. Both square and hexagonal arrays are considered. The size of the array required by these schemes to embed an N-node tree is O(N). The maximal distance in the array between two nodes adjacent in the tree is O(\(\sqrt{N})\). The sum of distances between all pairs of nodes adjacent in the tree is O(N). The modularity of our schemes, together with the intractability of the embedding problem, suggests that these schemes may serve as useful embedding patterns.