The detection of structure centerlines from imaging data plays a crucial role in the understanding, application and further analysis of many diverse problems, such as road mapping, crack detection, medical imaging and biometric identification. In each of these cases, pixel-wise segmentation is not sufficient to understand and quantify overall graph structure and connectivity without further processing that can lead to compound error. We thus require a method for automatic extraction of graph representations of patterning. In this paper, we propose a novel Deep Orientated Distance-transform Network (DODN), which predicts the centerline map and an orientated distance map, comprising orientation and distance in relation to the centerline and allowing exploitation of its geometric properties. This is refined by jointly modeling the relationship between neighboring pixels and connectivity to further enhance the estimated centerline and produce a graph of the structure. The proposed approach is evaluated on a diverse range of problems, including crack detection, road mapping and superficial vein centerline detection from infrared/ color images, improving over the state-of-the-art by 2.1%, 10.9% and 17.3%/ 4.6% respectively in terms of quality, demonstrating its generalizability and performance in a wide range of mapping problems.