As ecologists and foresters produce an increasing range of probabilistic data, mathematical techniques that address the fundamental interactions between stochastic events and spatial landscape features have the potential to provide valuable decision support in the sustainable management of natural resources. The heart of this thesis explores two models motivated by pressing environmental issues: limiting the spread of wildfire and invasive species containment. We formulate stochastic spatial models in graphs that capture key tradeoffs, and prove a number of original optimization results. Since even deterministic cases in highly-restricted graph classes are NP-Hard (that is, they can not efficiently be solved to optimality), our studies focus on approximation algorithms that efficiently produce solutions which are provably near-optimal. Our models also represent natural generalizations of ideas in the optimization and computer science literature. In particular, while much recent attention has been devoted to questions about connecting stochastically chosen sets, our applications in sustainable planning suggest extensions of deterministic graphcutting models; we explore novel problems in stochastic disconnection.