Motivation: To understand protein structure, folding and function fully and to design proteins de novo reliably, we must learn from natural protein structures that have been characterized experimentally. The number of protein structures available is large and growing exponentially, which makes this task challenging. Indeed, computational resources are becoming increasingly important for classifying and analyzing this resource. Here, we use tools from graph theory to define an Atlas classification scheme for automatically categorizing certain protein substructures. Results: Focusing on the a-helical coiled coils, which are ubiquitous protein-structure and protein- protein interaction motifs, we present a suite of computational resources designed for analyzing these assemblies. iSOCKET enables interactive analysis of side-chain packing within proteins to identify coiled coils automatically and with considerable user control. Applying a graph theory-based Atlas classification scheme to structures identified by iSOCKET gives the Atlas of Coiled Coils, a fully automated, updated overview of extant coiled coils. The utility of this approach is illustrated with the first formal classification of an emerging subclass of coiled coils called a-helical barrels. Furthermore, in the Atlas, the known coiled-coil universe is presented alongside a partial enumeration of the 'dark matter' of coiled-coil structures; i.e. those coiled-coil architectures that are theoretically possible but have not been observed to date, and thus present defined targets for protein design.