Communication aspects of networks based on geometric incidence relations (Q1119610)

We explore the communication properties of a family of networks, based on the incidence relation of the ``middle'' subspaces of a projective space. Network theoretic issues as well as implementation details are discussed. The networks are shown to be symmetric and nearly optimal in diameter. They support a natural routing scheme with efficient implementation of optimal complexity. An extremely high redundancy makes the networks robust. A parallel-routing algorithm is analysed and is shown to achieve running time O(diameter), which is also the lower bound.