|
In graph drawing, planarization is a method of extending drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph.〔.〕〔.〕 Planarization may be performed by using any method to find a drawing (with crossings) for the given graph, and then replacing each crossing point by a new artificial vertex, causing each crossed edge to be subdivided into a path. The original graph will be represented as a immersion minor of its planarization. In incremental planarization, the planarization process is split into two stages. First, a large planar subgraph is found within the given graph. Then, the remaining edges that are not already part of this subgraph are added back one at a time, and routed through an embedding of the planar subgraph. When one of these edges crosses an already-embedded edge, the two edges that cross are replaced by two-edge paths, with a new artificial vertex that represents the crossing point placed at the middle of both paths.〔〔 In some case a third local optimization stage is added to the planarization process, in which edges with many crossings are removed and re-added in an attempt to improve the planarization.〔 ==Finding the largest planar subgraph== Using incremental planarization for graph drawing is most effective when the first step of the process finds as large a planar graph as possible. Unfortunately, finding the planar subgraph with the maximum possible number of edges (the ''maximum planar subgraph'' problem〔.〕) is NP-hard, and MaxSNP-hard, implying that there probably does not exist a polynomial time algorithm that solves the problem exactly or that approximates it arbitrarily well.〔.〕 In an ''n''-vertex connected graph, the largest planar subgraph has at most 3''n'' − 6 edges, and any spanning tree forms a planar subgraph with ''n'' − 1 edges. Thus, it is easy to approximate the maximum planar subgraph within an approximation ratio of one-third, simply by finding a spanning tree. A better approximation ratio, 9/4, is known, based on a method for finding a large partial 2-tree as a subgraph of the given graph.〔〔 Alternatively, if it is expected that the planar subgraph will include almost all of the edges of the given graph, leaving only a small number ''k'' of non-planar edges for the incremental planarization process, then one can solve the problem exactly by using a fixed-parameter tractable algorithm whose running time is linear in the graph size but non-polynomial in the parameter ''k''.〔.〕 The problem may also be solved exactly by a branch and cut algorithm, with no guarantees on running time, but with good performance in practice.〔〔.〕 This parameter ''k'' is known as the skewness of the graph.〔 There has also been some study of a related problem, finding the largest planar induced subgraph of a given graph. Again, this is NP-hard, but fixed-parameter tractable when all but a few vertices belong to the induced subgraph.〔.〕 proved a tight bound of 3''n''/(Δ + 1) on the size of the largest planar induced subgraph, as a function of ''n'', the number of vertices in the given graph, and Δ, its maximum degree; their proof leads to a polynomial time algorithm for finding an induced subgraph of this size.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Planarization」の詳細全文を読む スポンサード リンク
|