In this article we propose a new method for automatic seismic zonation based on focal mechanisms. The technique searches for the areas where the homogeneity of the stress field is maximized. The problem is posed as one of optimal partitioning of the graph corresponding to the Delaunay triangulation of the available epicenters. Two alternative techniques are used: the first one limits the search to the partitions of the Euclidean minimum spanning tree (emst) of the triangulation; the other one uses a number of spanning trees that are variations of the emst. The optimization is performed using a genetic algorithm. The technique is applied to seismic zonation in northeastern Italy by using a set of 219 focal mechanisms. The results are compared with those of a nonautomatic zonation used to investigate the distribution of the stress and strain fields and performed taking into account tectonic structures, faulting patterns, spatial distribution of seismicity, and other geophysical data. The proposed method is shown to be effective in finding areas of homogeneous stress and providing evidence for critical zones of complex behavior.