Abstract In this work, we work on robust models, i.e. ones that incorporate uncertainty in the feasible set. The aim is to find a minimum-cost subgraph satisfying the connectivity requirement. Most existing models of robust network design assume uniform scenario sets. Our algorithm combines combinatorial and LP-based techniques. We are convinced our methods are suitable for solving other robust problems in... In this work, we work on robust models, i.e. ones that incorporate uncertainty in the feasible set. The aim is to find a minimum-cost subgraph satisfying the connectivity requirement. Most existing models of robust network design assume uniform scenario sets. Our algorithm combines combinatorial and LP-based techniques. We are convinced our methods are suitable for solving other robust problems in planar graphs. Read More Read Less