NC-APPROXIMATION SCHEMES FOR NP-HARD AND PSPACE-HARD PROBLEMS FOR GEOMETRIC GRAPHS

We present NC-approximation schemes for a number of graph problems whe n restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the sa me time versus performance trade-off as the best known approximation s chemes for planar graphs. We also define the concept of lambda-precisi on unit disk graphs and show that for such graphs the approximation sc hemes have a better time versus performance trade-off than the approxi mation schemes for arbitrary unit disk graphs. Moreover, compared to u nit disk graphs, we show that for lambda-precision unit disk graphs ma ny more graph problems have efficient approximation schemes. Our NC-ap proximation schemes can also be extended to obtain efficient NC-approx imation schemes for several PSPACE-hard problems on unit disk graphs s pecified using a restricted version of the hierarchical specification language of Bentley, Ottmann, and Widmayer. The approximation schemes for hierarchically specified unit disk graphs presented in this paper are among the first approximation schemes in the literature for natura l PSPACE-hard optimization problems. (C) 1998 Academic Press.