In the last decade, graph-cut optimization has been popular for a variety of pixel labeling problems. Typically graph-cut methods are used to incorporate a smoothness prior on a labeling. Recently several methods incorporated ordering constraints on labels for the application of object segmentation. An example of an ordering constraint is prohibiting a pixel with a car wheel label to be above a pixel with a car roof label. We observe that the commonly used graph-cut based expansion is more likely to get stuck in a local minimum when ordering constraints are used. For certain models with ordering constraints, we develop new graph-cut moves which we call order-preserving moves. Order-preserving moves act on all labels, unlike expansion. Although the global minimum is still not guaranteed, optimization with order-preserving moves performs significantly better than expansion. We evaluate orderpreserving moves for the geometric class scene labeling (introduced by Hoiem et al.) where the goal is to assign each pixel a label such as sky, ground, etc., so ordering constraints arise naturally. In addition, we use orderpreserving moves for certain simple shape priors in graphcut segmentation, which is a novel contribution in itself.