A great variety of problems involving parallel interconnection networks can be cast formally as questions about graphs. By bringing the tools of mathematics to bear on these questions, theoretical computer scientists now understand a great deal about VLSI layout of circuits on computer chips, fault-tolerance of networks, aspects of communication in networks, methods for comparing the relative strengths and weaknesses of networks, and other issues. A rich theory has emerged, but many interesting open questions in the above areas remain. The project examines a number of these questions.