MAXPLANAR : a graphical software package for testing maximal planar subgraph algorithms
Kedan Zhao · Montana State University ScholarWorks (Montana State University) · 1996
We present an efficient implementation of a software package, MAXPLA-NAR, with a user-friendly interface for several algorithms for finding maximal planar subgraphs of nonplanar graphs.The algorithms include the methods of path addition, edge addition, vertex addition, and cycle packing. MAXP LANAR is designed to facilitate graph input and output and algorithm efficiency analysis. The result is an easy-to-use software package for researchers to test the various planarization algorithms.Extensive empirical results are given for the heuristics on several families of nonplanar graphs.Type I are random nonplanar graphs with unknown maximum planar subgraph size.Type II are sparse, planar-like graphs which are graphs that are almost planar.Type III instances are dense graphs.Results of empirical testing show that the cycle-packing algorithm found the best solution in random nonplanar graphs, but it required much more CPU time than the other heuristics.The results also show that for planar-like graphs the vertex addition method is better than the edge addition method.However, for dense random graphs the edge addition method is better than others.vi B ibliography 71