We consider the task of planning smooth trajecto- ries for robot motion. In this paper we make two contributions. First we present a method for cubic spline optimization; this technique lets us simultaneously plan optimal task-space tra- jectories and fit cubic splines to the trajectories, while obeying many of the same constraints imposed by a typical motion planning algorithm. The method uses convex optimization techniques, and is therefore very fast and suitable for real-time re-planning and control. Second, we apply this approach to the tasks of planning foot and body trajectory for a quadruped robot, the “LittleDog,” and show that the proposed approach improves over previous work on this robot.