Peer-to-peer networks and mobile ad hoc networks are emerging distributed networks that share several similarities. Fundamental among these similarities is the decentralized role of each participating node to route messages on behalf of other nodes, and thereby, collectively realizing communication between any pair of nodes. Messages are routed on a topology graph that is determined by the peer relationship between nodes. Although routing is fairly straightforward when the topology graph is static, dynamic variations in the peer relationship that often occur in peer-to-peer and mobile ad hoc networks present challenges to routing. In this thesis, we examine the interplay between routing messages and network topology design in two classes of these networks -- unstructured peer-to-peer networks and sparsely-connected mobile ad hoc networks. In unstructured peer-to-peer networks, we add structure to overlay topologies to support file sharing. Specifically, we investigate the advantages of designing overlay topologies with small-world properties to improve (a) search protocol performance and (b) network utilization. We show, using simulation, that "small-world-like" overlay topologies where every node has many close neighbors and few random neighbors exhibit high chances of locating files close to the source of file search query. This improvement in search protocol performance is achieved while decreasing the traffic load on the links in the underlying network. In the context of sparsely-connected mobile ad hoc networks where nodes provide connectivity via mobility, we present a protocol for routing in space and time where the message forwarding decision involves not only where to forward (space), but also when to forward (time). We introduce space-time routing tables and develop methods to compute these routing tables for those instances of ad hoc networks where node mobility is predictable over either a finite horizon or indefinitely due to periodicity in node motion. Furthermore, when the node mobility is unpredictable, we investigate several forwarding heuristics to address the scarcity in transmission opportunities in these sparsely-connected ad hoc networks. In particular, we present the advantages of fragmenting messages and augmenting them with erasure codes to improve the end-to-end message delivery performance.