loading...
Three-Dimensional Embedding of Binary Trees
Dallas/Richardson, Texas, USA December 07-December 07
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2000.9002782000 International Symposium on Paral ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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 that 1. the number of nodes in the grid is at most 1.172 (1.25) times the number of nodes in the tree, and 2. 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.
Citation:
W. Bein, L. Larmore, C. Shields, Jr.,, H. Sudborough, "Three-Dimensional Embedding of Binary Trees," ispan, pp.140, 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), 2000
Usage of this product signifies your acceptance of the Terms of Use.