Trends in wireless networks are proceeding toward increasingly dense deployments, supporting resilient interconnection for applications that carry ever higher capacity and tighter latency requirements. These developments put increasing pressure on network backhaul and drive the need for a re-examination of traditional backhaul topologies. Challenges of impending networks cannot be tackled by star and ring approaches due to their lack of intrinsic survivability and resilience properties, respectively. In support of this re-examination, we formulate backhaul topology optimization as a graph optimization problem by capturing both the objective and constraints of optimization in graph invariants. Our graph theoretic approach leverages well studied mathematical techniques to provide a more systematic alternative to traditional approaches to backhaul design. Specifically, herein we optimize over some known graph invariants, such as maximum node degree, topology diameter, average distance, and edge betweenness, and also over a new invariant called node Wiener impact, in order to achieve baseline backhaul topologies that match the needs for resilient future networks.