  Designing well-connected graphs is a fundamental problem that frequently
arises in various contexts across science and engineering. The weighted number
of spanning trees, as a connectivity measure, emerges in numerous problems and
plays a key role in, e.g., network reliability under random edge failure,
estimation over networks and D-optimal experimental designs. This paper tackles
the open problem of designing graphs with the maximum weighted number of
spanning trees under various constraints. We reveal several new structures,
such as the log-submodularity of the weighted number of spanning trees in
connected graphs. We then exploit these structures and design a pair of
efficient approximation algorithms with performance guarantees and
near-optimality certificates. Our results can be readily applied to a wide
verity of applications involving graph synthesis and graph sparsification
scenarios.
