Steiner trees, partial 2–trees, and minimum IFI networks

Minimum isolated failure immune networks are shown to be 2–trees. Further, subgraphs of 2‐trees are shown to be exactly those graphs which contain no subgraph homeomorphic to the four‐vertex complete graph. Together, these two characterizations yield a linear time algorithm for adding lines to a network to produce a minimum isolated failure immune network, whenever this is possible. This same algorithm, in conjunction with a linear time Steiner tree algorithm for 2‐tress, yields a linear time Steiner tree algorithm for partial 2‐tress. This contrasts with the known NP‐completeness of the Steiner tree problem for planar graphs.