Most nonlinear data embedding methods use bottom-up approaches for capturing underlying structures of data distributed as points on nonlinear manifolds in high dimensional spaces. These methods usually start by designating neighbor points to each point. Neighbor points have to be designated in such a way that the constructed neighborhood graph is connected so that the data can be projected to a single global coordinate system. In this paper, we present an incremental method for updating neighborhood graphs. The method guarantees k-edge-connectivity of the constructed neighborhood graph. Together with incremental approaches for geodesic distance estimation and multidimensional scaling, our method enables incremental embedding of high dimensional data streams. The method works even when the data are under-sampled or non-uniformly distributed. It has important applications in the processing of data streams and multimedia data.