Decreasing gas prices and the pressing need for fast-responding electric power generators are currently transforming natural gas networks. The intermittent operation of gas-fired plants to balance wind generation introduces spatiotemporal fluctuations of increasing gas demand. At the heart of modeling, monitoring, and control of gas networks is a set of nonlinear equations relating nodal gas injections and pressures to flows over pipelines. Given gas demands at all points of the network, the gas flow task aims at finding the rest of the physical quantities. For a tree network, the problem enjoys a closed-form solution; yet solving the equations for practical meshed networks is non-trivial. This problem is posed here as a feasibility problem involving quadratic equalities and inequalities, and is further relaxed to a convex semidefinite program (SDP) minimization. Drawing parallels to the power flow problem, the relaxation is shown to be exact if the cost function is judiciously designed using a representative set of network states. Numerical tests on a Belgian gas network corroborate the superiority of the novel method in recovering the actual gas network state over a Newton-Raphson solver. This thesis also considers the coupled infrastructures of natural gas and electric power systems. The gas and electric networks are coupled through gas-fired generators, which serve as shoulder and peaking plants for the electric power system. The optimal dispatch of coupled natural gas and electric power systems is posed as a relaxed convex minimization problem, which is solved using the feasible point pursuit (FPP) algorithm. For a decentralized solution, the alternating direction method of multipliers (ADMM) is used in collaboration with the FPP. Numerical experiments conducted on a Belgian gas network connected to the IEEE 14 bus benchmark system corroborate significant enhancements on computational efficiency compared with the centralized FPP-based approach.