The maximum-weight-window problem of a planar graph

An undirected graph is called a planar graph if it can be drawn on a plane without the edges crossing, and such a drawing is called a planar drawing. Each region of the plane divided by a planar drawing is called a face, and the subgraph on the boundary of a face is called a window. Let G=(V,E) be a planar graph with vertex- and edge-weight. The sum of the weight of the vertices and edges on a window is called the weight of the window. A window having the maximum weight among all windows in planar drawings of G is called a maximum-weight-window of G. In this paper, the authors show that a planar drawing having a maximum-weight-window can be found in O(ℝVℝ+ℝEℝ) time even if the weight on vertices and edges may be negative. The proposed algorithm can be utilized in obtaining a maximal planar subgraph of a given non planar graph. [In Japanese.]