Map of Geometric Minimal Cuts for General Planar Embedding

详细信息    查看全文

• 作者：Lei Xu (19)
  Evanthia Papadopoulou (20)
  Jinhui Xu (19)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：8287
• 期：1
• 页码：250-259
• 全文大小：252KB
• 作者单位：Lei Xu (19)
  Evanthia Papadopoulou (20)
  Jinhui Xu (19)
  
  19. Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY, 14260, USA
  20. Faculty of Informatics, Universitdella Svizzera italiana, Via Giuseppe Buffi 13, CH 6904, Lugano, Switzerland
  
• ISSN：1611-3349

文摘

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) log2 N loglogN) time, where K is the complexity of the Hausdorff Voronoi diagram and N is the number of geometric minimal cuts.