Name
Abstract | ||
|---|---|---|
We describe total congestion 1 embeddings of complete binary trees into three dimensional grids with expansion ratios 1.172 and 1.25. That is, we give a one-to-one embedding of any complete binary tree into a hexahedron shaped grid such that1. the number of nodes in the grid is at most 1.172 (1.25) times the number of nodes in the tree, and2. no tree nodes or edges occupy the same grid positions.The first strategy embeds trees into cube shaped 3D grids. That is, 3D grids in which all dimensions are roughly equal, in size. The second strategy embeds trees into flat 3D grid shapes. That is, it maps complete binary trees into 3D grids with a fixed, small number of layers. An application suggests which embedding to use. For simulations in parallel computer environments, or possibly graph drawing, a cube shaped 3D grid is appropriate. For the sake of VLSI, or other graph drawing applications, embeddings with a small number of layers are better. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1109/ISPAN.2000.900278 | ISPAN |
Keywords | Field | DocType |
application software,graph drawing,circuits,computer simulation,three dimensional,vlsi,computer architecture,binary trees,concurrent computing,computer science,parallel algorithms,virtual machines,very large scale integration,parallel computer,computational modeling,tree graphs,binary tree | Graph drawing,Topology,Hexahedron,Embedding,Parallel algorithm,Computer science,Parallel computing,Binary tree,Very-large-scale integration,Grid,Cube | Conference |
ISBN | Citations | PageRank |
0-7695-0936-3 | 1 | 0.38 |
References | Authors | |
5 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wolfgang W. Bein | 1 | 194 | 29.68 |
| Lawrence L. Larmore | 2 | 859 | 109.15 |
| Charles Shields Jr | 3 | 2 | 1.47 |
| Ivan Hal Sudborough | 4 | 585 | 193.20 |