This chapter considers the problem of computing a map of geometric minimal cuts (called the MGMC problem): Given a graph G = (V, E) and a planar embedding of a subgraph H = (VH, EH), compute a map of geometric minimal cuts induced by axis-aligned rectangles in the embedding plane. The MGMC problem is motivated by the critical area extraction problem in VLSI design and finds applications in several other fields. This chapter surveys two different approaches for the MGMC problem, which are based on a mix of geometric and graph-algorithm techniques. It is first shown that, unlike the classic min-cut problem on graphs, the number of all possible rectilinear geometric minimal cuts is bounded by a low polynomial, O(n3). Based on this observation, the first approach enumerates all rectilinear geometric minimal cuts and computes their L∞ Hausdorff-Voronoi diagram. The second approach iteratively identifies relevant geometric minimal cuts and their Hausdorff-Voronoi diagram by iteratively constructing higher-order Voronoi diagrams. In the latter approach the embedding need not be rectilinear and may consist of arbitrary simple polygons. The chapter also presents the structural properties of the L∞ Hausdorff-Voronoi diagram of rectangles, which provides the map of the MGMC problem, and plane sweep algorithms for its construction.