We introduce a new class of graphs that we call cycletrees. A cycletree includes a basic binary tree and has a unique Hamiltonian cycle. We argue that cycletrees reﬂect the communication patterns of several common parallel programming paradigms and can be used in various ﬁelds of parallel computation. Several minimality, optimality and planarity properties are proved for cycletrees. A subclass of cycletrees is identiﬁed as natural cycletrees through an inductive deﬁnition. Methods for generating natural cycletrees, given either a set of vertices, a cycle or a basic binary tree, are presented. We present an inexpensive and simple routing algorithm for natural cycletree networks. A superfast parallel algorithm is presented, which dynamically establishes the shortest path router data for the given router algorithm. We compare cycletrees with other interconnection graphs that have been designed for partly similar reasons.