Planar chordal cycles: Their construction, applications and analysis in mesh networks

Abstract

We propose a novel idea for cycles that is based on the network topology in planar graphs. Using the graph theory terminology of chordal graphs, we call those cycles Planar Chordal Cycles (PCCs). Sufficient conditions are formulated to guarantee the existence of PCCs to cover a set of faces in the graph. These conditions to form a cycle are then mapped to the dual domain to reduce the complexity of cycle construction so that it is easier for identification and construction. This mapping is made possible by using a novel idea of constructing a dual graph that can capture the face connectivity in the original graph (and we call it the Modified Cycle Graph (MCG)). An algorithm based on some searching techniques and criteria is proposed to use those conditions to construct cycles with different objectives and properties. The application of PCCs in multicasting and mesh network protection are discussed. An efficiency and performance study has been conducted to compare this technique to other techniques. We have also analyzed performance measures for network cycle-based protection mechanisms. We present a detailed study and analysis on the restorability of a single protection cycle covering single-domain networks, and we also present the corresponding redundancy and protection path analysis. For two-domain networks that use a single cycle in each domain, we present an analytical model that extends the single domain idea by considering the shared edges between the two domains. Limited results have been obtained in special cases for more than two domains.