Polygon partitioning is an important problem in computational geometry with a long history. In this paper we consider the problem of partitioning a polygon with holes into a minimum number of uniformly monotone components allowing arbitrary Steiner points. We call this the MUMC problem. We show that, given a polygon with n vertices and h holes and a scan direction, the MUMC problem relative to this direction can be solved in time O(nlogn+hlog^3h). Our algorithm produces a compressed representation of the subdivision of size O(n), from which it is possible to extract either the entire decomposition or just the boundary of any desired component, in time proportional to the output size. When the scan direction is not given, the problem can be solved in time O(K(nlogn+hlog^3h)), where K is the number of edges in the polygon's visibility graph. Our approach is quite different from existing algorithms for monotone decomposition. We show that in O(nlogn) time the problem can be reduced to the problem of computing a maximum flow in a planar network of size O(h) with multiple sources and multiple sinks. The problem is then solved by applying any standard network flow algorithm to the resulting network. We also present a practical heuristic for reducing the number of Steiner points.