This dissertation studies graph-structured nonlinear programs, nonlinear optimization problems whose algebraic structures are induced by graphs. A graph-structured nonlinear program is a generalized abstraction for dynamic optimization, stochastic optimization, optimization with embedded partial differential equations, and network system optimization. This generalized abstraction allows studying properties these problems share in common and creating tailored solution algorithms. In the first part, we study the fundamental property of solutions of graph-structured nonlinear programs. Specifically, we study how strongly a nodal parametric perturbation influences the nodal solution of another node. Building upon existing nonlinear programming sensitivity theory, we prove that solution sensitivity decays exponentially with the distance from the perturbation point on the graph. Remarkably, this result, which we call the exponential decay of sensitivity, holds under fairly standard assumptions used in classical nonlinear programming sensitivity theory: strong second-order sufficiency conditions and linear independence constraint qualifications. In addition, we establish uniform regularity conditions, the sufficient conditions under which the sensitivity decay rate remains uniformly bounded (independent of the size of the problem). Such uniformity allows studying sensitivity behaviors of problems with arbitrarily large graphs. The exponential decay of sensitivity enables the creation of a specialized decomposition method for graph-structured nonlinear programs, the overlapping Schwarz method. In the second part, we study the convergence properties and implementation of this method. The overlapping Schwarz method has been traditionally used for the solution of sparse linear systems, which typically arise in discretized partial differential equations. In this work, we generalize this algorithm for graph-structured nonlinear programs. The proposed overlapping Schwarz algorithm partitions the original graph domain into a set of overlapping subdomains, which yields a set of coupled subproblems, and solves the subproblems in parallel and iteratively with the exchange of solution information at the boundary. The overlap is a crucial element in this method. Based on the exponential decay of sensitivity, we show that the algorithm locally converges if the overlap is sufficiently large and that the convergence rate improves exponentially with the size of overlap under certain conditions. We discuss several different variations of implementing the overlapping Schwarz method (problem level, subproblem level, and linear algebra level). Finally, with diverse numerical examples, we demonstrate the effectiveness of the proposed method.