The connectivity service provided by connectivity coordinator 114 may include a number of techniques implemented to help clients of the provider network establish and manage dedicated network paths from the client networks 162 to the resource collections 120 in various embodiments. For example, a cross-network connection 191 including a physical link or cable between client-side router 142B and endpoint router 132B may have been established with the help of some of the features of the connectivity service provided by connectivity coordinator 114. The term cross-network connection, as used herein, refers to a physical network connection set up between two autonomous networks. For example, within the Internet, an autonomous network may be identified by a unique Autonomous System (AS) identifier—a collection of connected Internet Protocol (IP) routing prefixes under the control of one or more network operators that presents a common, clearly defined routing policy to the Internet. In the illustrated embodiment, the connectivity coordinator 114 may be operable to implement an interface defining various connectivity operations available to clients, including establishment of cross-network connections such as connection 191, and establishment of logically isolated connections or paths using such cross-network links. The interface may be implemented using a variety of approaches: e.g., as an application programming interface (API), a web-based interface, other graphical user interfaces, or command-line interfaces, in different embodiments. Connectivity coordinator 114 may also make the interface known to clients using various mechanisms—e.g., a notification detailing the interface may be published on one or more corporate web sites in one embodiment. Connectivity coordinator 114 may itself be resident outside provider network 105 in some embodiments, and in other embodiments it may be incorporated within the provider network 105.