We propose a novel approach to analyze and visualize residue contact networks of protein interfaces by graph-based algorithms using a minimum cut tree (mincut tree). Edges in the network are weighted according to an energy function derived from knowledge-based potentials. The mincut tree, which is constructed from the weighted residue network, simplifies and summarizes the complex structure of the contact network by an efficient and informative representation. This representation offers a comprehensible view of critical residues and facilitates the inspection of their organization. We observed, on a nonredundant data set of 38 protein complexes with experimental hotspots that the highest degree node in the mincut tree usually corresponds to an experimental hotspot. Further, hotspots are found in a few paths in the mincut tree. In addition, we examine the organization of hotspots (hot regions) using an iterative clustering algorithm on two different case studies. We find that distinct hot regions are located on specific sites of the mincut tree and some critical residues hold these clusters together. Clustering of the interface residues provides information about the relation of hot regions with each other. Our new approach is useful at the molecular level for both identification of critical paths in the protein interfaces and extraction of hot regions by clustering of the interface residues. Proteins 2010; 78:2283-2294. (C) 2010 Wiley-Liss, Inc.