We study the multi-frame structure of motion problems when the camera translates on a plane with small baselines and arbitrary rotations. This case shows up in many practical applications, for example, in ground robot navigation. We consider the framework for small baselines presented in , in which a factorization method is used to compute the structure and motion parameters accurately, efficiently, and with guaranteed convergence. When the camera translates on a plane, the algorithm in  cannot be applied because the estimation matrix drops rank, causing the equations to no longer be linear. In this project, we show how to linearly solve those equations while preserving the accuracy, speed, and convergence properties of the non-planar algorithm. We evaluate the proposed algorithms on synthetic and real image sequences, and compare our results with those of the optimal algorithm. The proposed algorithms are very fast, accurate, have less than 0.3% outliers, work well for small-to-medium baselines and non-planar as well as planar motions.