Interplanetary communication networks comprise orbiters, deep‐space relays, and stations on planetary surfaces. These networks must overcome node mobility, constrained resources, and significant propagation delays. Opportunities for wireless contact rely on calculating transmit and receive opportunities, but the Euclidean‐distance diameter of these networks (measured in light‐seconds and light‐minutes) precludes node discovery and contact negotiation. Propagation delay may be larger than the line‐of‐sight contact between nodes. For example, Mars and Earth orbiters may be separated by up to 20.8min of signal propagation time. Such spacecraft may never share line‐of‐sight, but may uni‐directionally communicate if one orbiter knows the other's future position. The Contact Graph Routing (CGR) approach is a family of algorithms presented to solve the messaging problem of interplanetary communications. These algorithms exploit networks where nodes exhibit deterministic mobility. For CGR, mobility and bandwidth information is pre‐configured throughout the network allowing nodes to construct transmit opportunities. Once constructed, routing algorithms operate on this contact graph to build an efficient path through the network. The interpretation of the contact graph, and the construction of a bounded approximate path, is critically important for adoption in operational systems. Brute force approaches, while effective in small networks, are computationally expensive and will not scale. Methods of inferring cycles or other librations within the graph are difficult to detect and will guide the practical implementation of any routing algorithm. This paper presents a mathematical analysis of a multi‐destination contact graph algorithm (MD‐CGR), demonstrates that it is NP‐complete, and proposes realistic constraints that make the problem solvable in polynomial time, as is the case with the originally proposed CGR algorithm. An analysis of path construction to complement hop‐by‐hop forwarding is presented as the CGR‐EB algorithm. Future work is proposed to handle the presence of dynamic changes to the network, as produced by congestion, link disruption, and errors in the contact graph. We conclude that pre‐computation, and thus CGR style algorithms, is the only efficient method of routing in a multi‐node, multi‐path interplanetary network and that algorithmic analysis is the key to its implementation in operational systems.
