An <i>O</i> ( <i>n</i> log <i>n</i> ) approximation scheme for Steiner tree in planar graphs

Abstract

We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O ( n log n ).