We present a new methodology for computing approximate Nash equilibria for two-person non-cooperative games basedupon certain extensions and specializations of an existing optimization approach previously used for the derivation of fixed approximations for this problem. In particular, the general two-person problem is reduced to an indefinite quadratic programming problem of special structure involving the nn adjacency matrix of an induced simple graph specified by the input data of the game, where n is the number of players' strategies. Using this methodology and exploiting certain properties of the positive part of the spectrum of the induced graph, we show that for any 0">0 there is an algorithm to compute an -approximate Nash equilibrium in time n(m) , where, (m)=mi=1in and 12m are the positive eigenvalues of the adjacency matrix of the graph. For classes of games for which (m) is a constant, there is a PTAS. Based on the best upper bound derived for (m) so far, the worst case complexity of the method is bounded by the subexponential nm .