  " How well connected is the network? " This is one of the most fundamental
questions one would ask when facing the challenge of designing a communication
network. Three major notions of connectivity have been considered in the
literature, but in the context of traditional (single-layer) networks, they
turn out to be equivalent. This paper introduces a model for studying the three
notions of connectivity in multi-layer networks. Using this model, it is easy
to demonstrate that in multi-layer networks the three notions may differ
dramatically. Unfortunately, in contrast to the single-layer case, where the
values of the three connectivity notions can be computed efficiently, it has
been recently shown in the context of WDM networks (results that can be easily
translated to our model) that the values of two of these notions of
connectivity are hard to compute or even approximate in multi-layer networks.
The current paper shed some positive light into the multi-layer connectivity
topic: we show that the value of the third connectivity notion can be computed
in polynomial time and develop an approximation for the construction of well
connected overlay networks.
