We present efficient algorithms for solving the piecewise-cubic approximation problems in the plane. Given a set D of n points in the plane, we find a piecewise-cubic polynomial curve passing through only the points of a subset S of D and approximating the other points using the uniform metric. The goal is to minimize the size of S for a given error tolerance $varepsilon$, called the min-# problem, or to minimize the error tolerance $varepsilon$ for a given size of S, called the min-$varepsilon$ problem. We give algorithms with running times O($n^2$ logn) and O($n^3$) for both problems, respectively.