Graph-cut optimization has been popular for a variety of labeling problems. Typically graph-cut methods are used to incorporate smoothness constraints on a labeling, namely most nearby pixels are encouraged to have similar labels. In addition to smoothness, ordering constraints on labels are also useful. For example, in object segmentation, a pixel with a car wheel label may be prohibited above a pixel with a car roof label. We observe that the commonly used graph-cut alpha-expansion move algorithm is more likely to get stuck in a local minimum when ordering constraints are used. For a certain model with ordering constraints, we develop new graph-cut moves which we call order-preserving. The advantage of order-preserving moves is that they act on all labels simultaneously, unlike alpha-expansion. More importantly, for most labels alpha, the set of alpha-expansion moves is strictly smaller than the set of order-preserving moves. This explains why in practice optimization with order-preserving moves performs significantly better than expansion in presence of ordering constraints. We evaluate order-preserving moves for the geometric class scene labeling, where the goal is to assign each pixel a label such as sky, ground, etc., so ordering constraints arise naturally. In addition, we use order-preserving moves for certain simple shape priors in segmentation, which is a novel contribution.