A simulated annealing algorithm for the maximum planar subgraph problem

References

• Jünger , M. and Mutzel , P. (1996) . Maximum planar subgraph and nice embeddings: Practical layout tools . Algorithmica , 16 : 33 – 59 .
   Google Scholar
• Di Battista G. Eades P. Tamassia R. Tollis I. (1999) Graph Drawing Prentice Hall
   Google Scholar
• Hasan , M. and Osman , I. (1995) . Local search algorithms for the maximal planar layout problem . Int. Trans. Oper. Res. , 2–1 : 89 – 106 .
   Google Scholar
• Liebers , A. (2001) . Planarizing graphs—a survey and annotated bibliography . J. Graph Algorithms Appl. , 5–1 : 1 – 74 .
   Google Scholar
• Vrtó I. (2003) Crossing numbers of graphs: A bibliography Available electronically atftp://ifi.savba.sk/pub/imrich/crobib.ps.gz
   Google Scholar
• Harary F. (1971) Graph Theory Addison-Wesley
   Google Scholar
• Mutzel , P. , Odenthal , T. and Scharbrodt , M. (1998) . The thickness of graphs: a survey . Graphs Comb. , 14 : 59 – 73 .
   Web of Science ®Google Scholar
• Dean , A. M. , Hutchinson , J. and Scheinerman , E. (1991) . On the thickness and arboricity of a graph . J. Comb. Theory Ser. B , 52 : 147 – 151 .
   Google Scholar
• Liu P. Geldmacher R. (1977) On the deletion of nonplanar edges of a graph In: Proc. 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing 727 738
   Google Scholar
• Yannakakis M. (1978) Node- and edge-deletion NP-complete problems. In: Proc. 10th Annual ACM Symposium on Theory of Computing . 253–264
   Google Scholar
• Booth , K. and Lueker , G. (1976) . Testing for the consecutive ones property, interval graphs, and graph planarity testing using PQ-tree algorithms . J. Comput. System Sci. , 13 : 335 – 379 .
   Web of Science ®Google Scholar
• Hopcroft , J. and Tarjan , R. (1974) . Efficient planarity testing . J. ACM , 21 : 549 – 568 .
   Web of Science ®Google Scholar
• Boyer J. Myrvold W. (1999) Stop minding your P's and Q's: A simplified O(n) planar embedding algorithm In: Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms 140 146
   Google Scholar
• Shih , W.-K. and Hsu , W.-L. (1999) . A new planarity test . Theor. Comput. Sci. , 223 : 179 – 191 .
   Web of Science ®Google Scholar
• Cimikowski , R. (1997) . An analysis of heuristics for the maximum planar subgraph problem . J. Inf. Opt. Science , 18 : 49 – 73 .
   Google Scholar
• Cimikowski , R. and Coppersmith , D. (1996) . The sizes of maximal planar, outerplanar, and bipartite planar subgraphs . Discr. Math. , 149 : 303 – 309 .
   Web of Science ®Google Scholar
• Cimikowski R. (1992) Graph planarization and skewness In: Proc. of the 23rd Southeastern Internation Conference on Combinatorics, Graph Theory, and Computing 21 32
   Google Scholar
• Cimikowski R. (1995) An analysis of some heuristics for the maximum planar subgraph problem In: Proc. of the 6th ACM-SIAM Symposium on Discrete Algorithms 322 331
   Google Scholar
• linescu , G. , Fernandes , C. , Finkler , U. and Karloff , H. (1998) . A better approximation algorithm for finding planar subgraphs . J. Algorithms , 27 : 269 – 302 .
   Google Scholar
• Cimikowski , R. (1994) . Branch-and-bound techniques for the maximum planar subgraph problem . Int. J. Comput. Math. , 53 : 135 – 147 .
   Web of Science ®Google Scholar
• Cimikowski , R. (1995) . On heuristics for determining the thickness of a graph . Info. Sci. , 85 : 87 – 98 .
   Google Scholar
• Aragon , C. R. , Johnson , D. S. , McGeoch , L. A. and Schevon , C. (1991) . Optimization by simulated annealing: An experimental evaluation; part II, graph coloring and number partitioning . Oper. Res. , 3–39 : 378 – 406 .
   Google Scholar
• Johnson , D. S. , Aragon , C. R. , McGeoch , L. A. and Schevon , C. (1989) . Optimization by simulated annealing: An experimental evaluation; part I, graph partitioning . Oper. Res. , 37 : 865 – 892 .
   Web of Science ®Google Scholar
• Reeves C. (Ed.) (1995) Modern Heuristic Techniques for Combinatorial Problems McGraw-Hill
   Google Scholar
• Goldschmidt , O. and Takvorian , A. (1994) . An efficient graph planarization two-phase heuristic . Networks , 24 : 69 – 73 .
   Web of Science ®Google Scholar
• Takefuji , Y. and Lee , K. (1989) . A near-optimum parallel planarization algorithm . Science , 245 : 1221 – 1223 .
   Google Scholar
• Resende , M. and Ribeiro , C. (1997) . A GRASP for graph planarization . Networks , 29 : 173 – 189 .
   Google Scholar
• Pitsoulis L. Resende M. (2002) Greedy randomized adaptive search procedures In: P. Pardalos and M. Resende (Eds.) Handbook of Applied Optimization Oxford University Press pp. 168–183
   Google Scholar
• Sarrafzadeh , M. and Lee , D. (1989) . A new approach to topological via minimization . IEEE Trans. Comput. Aid. Des. , 8 : 890 – 900 .
   Google Scholar
• Metropolis , N. , Rosenbluth , A. , Rosenbluth , M. , Teller , A. and Teller , E. (1953) . Equation of state calculation by fast computing machines . J. Chem. Phys. , 21 : 1087 – 1091 .
   Web of Science ®Google Scholar
• van Laarhoven P. Aarts E. (1987) Simulated Annealing: Theory and Applications Kluwer
   Google Scholar
• Aarts E. Lenstra J. (1997) Local Search in Combinatorial Optimization John Wiley and Sons
   Google Scholar
• LEDA version 4.3 (commercial) (2002) Available athttp://www.algorithmic-solutions.com
   Google Scholar
• Johnson D. (2002) A theoretician's guide to the experimental analysis of algorithms In: Proc. of the 5th and 6th DIMACS Implementation Challenges 215 250
   Google Scholar
• Mutzel P. (1994) The Maximum Planar Subgraph Problem PhD thesis Universität zu Köln
   Google Scholar
• Galil , Z. , Italiano , G. and Sarnak , N. (1999) . Fully dynamic planarity testing with applications . J. ACM , 46–1 : 28 – 91 .
   Google Scholar