We present the embedded trees algorithm, an iterative technique for estimation of Gaussian processes defined on arbitrary graphs. By exactly solving a series of modified problems on embedded span(cid:173) ning trees, it computes the conditional means with an efficiency comparable to or better than other techniques. Unlike other meth(cid:173) ods, the embedded trees algorithm also computes exact error co(cid:173) variances. The error covariance computation is most efficient for graphs in which removing a small number of edges reveals an em(cid:173) bedded tree. In this context, we demonstrate that sparse loopy graphs can provide a significant increase in modeling power rela(cid:173) tive to trees, with only a minor increase in estimation complexity.