The trade-off between directness and coverage in transport network growth

Designing spatial networks, such as transport networks, commonly deals with theproblem of how to best connect a set of locations through a set of links. In practice,it can be crucial to order the implementation of the links in a way that facilitatesearly functioning of the network during growth, like in bicycle networks. However,it is unclear how this early functional structure can be achieved by different growthprocesses. Here, we systematically study the growth of connected planar networks,quantifying functionality of the growing network structure. We compare randomgrowth with various greedy and human-designed, manual growth strategies. Weevaluate our results via the fundamental performance metrics of directness andcoverage, finding non-trivial trade-offs between them. Manual strategies fare betterthan greedy strategies on both metrics, while random strategies perform worstand are unlikely to be Pareto efficient. Centrality-based greedy strategies tend toperform best for directness but are worse than random strategies for coverage, whilecoverage-based greedy strategies can achieve maximum global coverage as fast aspossible but perform as poorly for directness as random strategies. Directness-basedgreedy strategies get stuck in local optimum traps. These results hold for a number ofstylized urban transport network topologies. Our insights are crucial for applicationswhere the order in which links are added to a spatial network is important, such as inurban or regional transport network design problems.