Reconstructing complex curvilinear structures such as neural circuits, road networks, and blood vessels is a key challenge in many scientific and engineering fields. It has a broad range of applications, from the delineation of micrometer-sized neurons in micrographs to the detection of Earth-sized solar filaments in telescope images. Modern data acquisition systems can produce very large volumes of such imagery in a short period of time. However, despite the abundance of available imagery and the ever-growing demand driven by the applications, existing reconstruction techniques are not robust to noisy and complex data, and require extensive manual intervention that is both time-consuming and tedious. In this thesis, we propose semi-and fully-automated approaches to overcome these limitations. To this end, we first present a novel filtering method that enhances irregular curvilinear structures in noisy image stacks. Unlike earlier approaches that rely on over-simplistic shape models for the structures and that work only on gray-scale images, ours exploits the color information and allows for the arbitrarily-shaped structures that are prevalent in biological imagery. We build a complete semi-automated reconstruction system based on this filtering approach and use it to collect highly accurate delineations from a wide range of datasets. We then propose a novel probabilistic algorithm to automate reconstruction, which uses these delineations as training data to compute, at each image pixel, the likelihood that the pixel is on the centerline of a curvilinear structure. Our algorithm first builds a graph of potential paths using these likelihoods and then seeks to find the tree that best explains the image data and that has spatially smooth branches. In contrast to other graph-based approaches that first span all the vertices and then prune some of the spurious branches using a heuristic procedure, ours selects an appropriate subset of the vertices to be spanned by optimizing a global objective function that explicitly models spurious branches, and combines the data likelihood with a geometric prior. A major limitation common to all graph-based approaches, including this one, is that they model the curvilinear networks as tree structures, which does not apply to many interesting networks such as roads and blood vessels. Furthermore, they rely on heuristic optimization algorithms, which do not provide optimality guarantees. Finally, the data terms in their objective functions are relatively local and have very little informative value. To address these limitations, we propose a new supervised Bayesian approach, which uses path classifiers trained on global appearance and path geometry features, and a Mixed Integer Programming formulation to guarantee optimality of the resulting solutions. Unlike all previous approaches, ours explicitly models the fact that the networks may be cyclic and allows graph vertices to be used more than once, subject to structural and topological constraints. We demonstrate the effectiveness of our approaches on a variety of challenging gray-scale and color datasets including aerial images of road networks and micrographs of neural arbors, and show that they outperform state-of-the-art techniques.