Efficient algorithms for reliability analysis of planar networks - a survey

We survey some recent polynomial-time algorithms for the exact computation of network reliability. The algorithms apply to several classes of planar networks, which include series-parallel, inner-cycle-free, inner-four-cycle-free and planar cube-free. We describe these classes and discuss the related polynomial algorithms for computing their reliability.