y

We dene the higher dimensional honeycomb graphs as a generalization of hexagonal plane tessellation, and consider it as a multiprocessor interconnection network. A 3-D honeycomb mesh network with n nodes has degree 4 and diameter approximately 3:63 3 p n. The network cost, dened as the product of degree and diameter, is about 20 percents better for the 3-D honeycomb than for the 3-D mesh. We describe the labeling scheme, the routing and broadcasting algorithms for three-dimensional and higher dimensional honeycombs. Furthermore, a formula for the diameter of a higher dimensional honeycomb network of given size is determined