In this talk, we introduce an interesting geometric graph called multi-column graph in the d-dimensional space (d ≥ 3), and formulate two related combinatorial optimization problems called optimal net subgraph problems on such graphs. Our formulations model a number of applied problems such as medical image segmentation, surface reconstruction with a given topology, and metric labeling. We prove that the optimal net subgraph problems on general d-D multi-column graphs (d ≥ 3) are NP-hard. For several important special cases of these problems in d-D (d ≥ 3) that arise in real applications, we present deterministic polynomial time algorithms for computing optimal solutions. Our algorithmic techniques enable us to achieve optimal solutions for several applied problems in polynomial time, such as some surface reconstruction problems in 3-D and 4-D and medical image segmentation problems in 3-D and 4-D. It is interesting to note that a previous belief was that some of these applied problems were NP-hard, and the previously best known exact algorithms for these problems, even on relatively simple cases, take at least exponential time. Our approaches can be extended to higher dimensions and to other more challenging versions. Experimental results on segmenting real medical images have shown the effectiveness and efficiency of our algorithms.