Map of geometric minimal cuts for general planar embedding

In this paper, we consider the problem of computing the map of geometric minimal cuts (MGMC) induced by a general planar embedding (i.e., the edge orientation is either rectilinear or diagonal) of a subgraph H = (V_H, E_H) of an input graph G = (V, E). The MGMC problem is motivated by the critical area extraction problem in VLSI layout and finds applications in several other areas. In this paper, we extend an earlier result for planar rectilinear embedding to its more general case. The increased freedom on edge orientation in the embedding imposes new challenges, mainly due to the fact that the inducing region of a geometric minimal cut is no longer unique. We show that the MGMC problem can be solved by computing the L_∞ Hausdorff Voronoi diagram of a set of rectangle families, each containing an infinite number of axis-aligned rectangles. By exploiting the geometric properties of these rectangle families, we present an output-sensitive algorithm for computing the Hausdorff Voronoi diagram in this general case which runs in O((N + K) log² N log log N) time, where K is the complexity of the Hausdorff Voronoi diagram and N is the number of geometric minimal cuts.