An analysis of some heuristics for the maximum planar subgraph problem
Robert J. Cimikowski · 1995
Introduction The problem of extracting a maximum planar subgraph from a nonplanar graph, referred to as graph planarization, has important applications in circuit layout, facility layout, and automated graphical display systems [F, TDB]. The problem is NP-hard [LG]; hence, research has focused on heuristics. There are several algorithms for finding maximal planar subgraphs [CHT, CNS, GT, JTS, JM, K, OT]. However, there are graphs (see [CC]) for which the size ratio between two maximal planar subgraphs can be as small as 1=3. Hence, unless some precautions are taken to avoid the extraction of small subgraphs, these heuristics have the potential for poor behavior. In this paper, we analyze the worst-case performance of some heuristics and show that there are graphs which can cause each of them to achieve the 1=3 bound. However, a theoretical analysis of an algorithm's performance is often too pessimistic and somew