Augmented Ring Networks TITLE2
William A. Aiello, Sandeep N. Bhatt, Fan Chung, A. L. Rosenber, Ramesh K. Sitaraman · 1997
We study three augmentations of ring networks that are intended to decrease a ring''s diameter significantly while increasing its structural complexity only modestly. Chordal rings enhance a ring network by adding noncrossing ``shortcut'''' edges, which can be viewed as chords of the ring. Express rings are chordal rings whose chords are oriented either clockwise or counterclockwise, allowing them to be viewed as (noncrossing) arcs of the ring. Multi-rings append subsidiary rings to edges of a ring and, recursively, to edges of appended subrings. Important measures of structural complexity are: the cutwidth of an express ring, viz., the maximum number of arcs that cross ``above'''' any ring edge (counting the edge itself); the depth of a multi-ring, viz., the level of recursive appending of subsidiary subrings. Our first result demonstrates the topological equivalence of these three modes of augmentation: for each augmented ring of one type, there are (graph-theoretically) isomorphic augmented rings of each of the other types; moreover, the cutwidth of an express ring is the depth of its isomorphic multi-ring, and vice versa. Our second focus is on the question of how much decrease in diameter is achievable for a given increase in structural complexity. We establish a tight diameter-cutwidth tradeoff for express rings: for each N and c, we exhibit a cutwidth-c, N-node express ring whose diameter is at most 2^{-1/c} cN^{1/c}; and, we prove that no such express ring can have diameter smaller than (4e)^{-1} c N^{1/c} - c/2. Finally, we prove that our (nontraditional) insistence that the arcs in an express ring of given cutwidth be noncrossing at most doubles the diameter of the augmented ring.