Algorithms for solving problems in optimization, enumeration, reliability design, statistical mechanics and electronics will be studied on classes of planar and near-planar graphs. The three main tools used to solve these problems are (1) the delta-wye reduction (DWR) algorithm -- which reduces a planar graph to a single edge by means of six elementary local tranformations, (2) the Erickson-Monma-Veinott (EMV) algorithm -- a dynamic programming algorithm that builds plane solution subgraphs up by patching together smaller subgraphs, and (3) the shortest enclosing walk (SEW) algorithm -- which encloses specified regions of the plane by a minimum length walk. The main concentration will be in the following area: reliability and associated enumeration problems, approximations schemes will be developed using the DWR algorithm to compute various measures of connectivity, Steiner trees and related network design problem, Ising models in statistical physics, and extensions and generalizations.
