Branch-and-bound techniques for the maximum planar subgraph problemFootnote^∗

^∗ Supported by a grant from the Engineering Experiment Station, Montana State University

References

• Abe , S. , Chiba , N. , Nishizeki , T. and Ozawa , T. 1985 . A linear algorithm for embedding planar graphs using PQ-trees . J. Comput. Sys. Sci. , 30 : 54 – 76 .
   Google Scholar
• Akl , S. 1981 . A comparison of combination generation methods . ACM Trans, on Math. Software , 7 ( 1 ) : 42 – 45 .
   Web of Science ®Google Scholar
• Balas , E. and Yu , C. S. 1986 . Finding a maximum clique in an arbitrary graph . SIAM J. Comput. , 15 ( 1 ) : 1054 – 1068 .
   Web of Science ®Google Scholar
• Booth , K. and Lueker , G. 1976 . Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms . J. Comput. Sys. Sci. , 1 ( 1 ) : 335 – 379 .
   Web of Science ®Google Scholar
• Cai , J. , Han , X. and Tarjan , R. E. 1993 . An O(mlog n)-time algorithm for the maximal planar subgraph problem . SIAM J. Comput. , 26 ( 6 ) : 1142 – 1162 .
   Web of Science ®Google Scholar
• Chiba , T. , Nishioka , I. and Shirakawa , I. 1979 . Proc, 1979 IEEE Symp. on Circiuts & Systems . An algorithm of maximal planarization of graphs . 1979 . pp. 649 – 652 .
   Google Scholar
• Cimikowski R.J. An empirical analysis of some graph planarization heuristics To appear in Alg orithmica.
   Google Scholar
• Di Battista , G. and Tamassia , R. 1989 . Proc, 30th. IEEE Symp. on Found, of Comput. Sci. . Incremental planarity testing . 1989 . pp. 436 – 441 .
   Google Scholar
• Foulds , L. R. , Gibbons , P. B. and Giffin , J. W. 1985 . Facilities layout adjacency determination: an experimental comparison of three graph theoretic heuristics . Oper. Res. , 33 1091 – 1106 .
   Web of Science ®Google Scholar
• Foulds , L. R. and Robinson , D. F. 1978 . Graph theoretic heuristics for the plant layout problem . Int. J. Prod. Res. , 16 27 – 37 .
   Web of Science ®Google Scholar
• Frederickson , G. N. 1984 . On linear-time algorithms for 5-coloring planar graphs . Info. Proc. Letters , 19 219 – 224 .
   Google Scholar
• Galil , Z. and Italiano , G. F. 1992 . Proc, 24th. ACM Symp. on Theory of Comput. . Fully Dynamic Planarity Testing . 1992 . pp. 301 – 311 .
   Google Scholar
• Goldschmidt O. Takvorian A. An efficient graph planarization two-phase heuristic To appear in Networks.
   Google Scholar
• Harary , F. 1969 . Graph Theory. , Reading, MA : Addison-Wesley .
   Google Scholar
• Hassan , M. M. and Hogg , G. L. 1987 . A review of graph theory application to the facilities layout problem . OMEGA Int. J. Management , 15 : 291 – 300 .
   Web of Science ®Google Scholar
• Hopcroft , J. and Tarjan , R. E. 1974 . Efficient planarity testing . J. Assoc. Comput. Mach. , 21 : 549 – 568 .
   Web of Science ®Google Scholar
• Jayakumar , R. , Thulasiraman , K. and Swamy , M. N. S. 1989 . O(n 2) algorithms for graph planarization . IEEE Trans. Comput.-Aided Design , 8 : 257 – 267 .
   Web of Science ®Google Scholar
• Kant G. An 0(n2) maximal planarization algorithm based on PQ-trees Tech. Report RUU-CS-92-03 Comput. Sci. Dept., Univ. Utrecht Netherlands January 1992
   Google Scholar
• Kernighan , B. W. and Lin , S. 1970 . An efficient heuristic procedure for partitioning graphs . Bell Sys. Tech. J. , 49 : 291 – 307 .
   Google Scholar
• Lempel , A. , Even , S. and Cedarbaum , I. 1966 . Proc, Theory of Graphs Int. Symp. . An algorithm for planarity testing of graphs . 1966 , Rome. pp. 215 – 232 .
   Google Scholar
• Lipton , R. J. and Miller , R. E. 1978 . A batching method for coloring planar graphs . Info. Proc. Letters , 7 185 – 188 .
   Google Scholar
• Liu , P. C. and Geldmacher , R. C. 1977 . Proc, 10th. S-E Conf. on Comb., Graph Theory, and Comput. . On the deletion of nonplanar edges of a graph . 1977 . pp. 727 – 738 .
   Google Scholar
• Matula D.W. Shiloach Y. Tarjan R.E. Two linear-time algorithms for 5-coloring a planar graph Tech. Report Stanford Univ 1980
   Google Scholar
• Mifsud , C. J. 1963 . Algorithm 154: Combinations in lexicographical order . Comm. Assoc. Comput. Mack , 6 ( 3 ) 103 – 103 .
   Google Scholar
• Ozawa , T. and Takahashi , H. 1981 . “ A graph planarization algorithm and its application to random graphs ” . In Lecture Notes in Computer Science 108 , 95 – 107 . New York : Springer-Verlag .
   Google Scholar
• Pardalos , P. M. and Desai , N. 1991 . An algorithm for finding a maximum weighted independent set in an arbitrary graph . Int. J. Computer Math , 38 : 163 – 175 .
   Web of Science ®Google Scholar
• Tamassia , R. , Di Battista , G. and Batini , C. 1988 . Automatic graph drawing and readability of diagrams . IEEE Trans. Sys., Man and Cyber. , 18 : 61 – 79 .
   Web of Science ®Google Scholar
• Tarjan , R. E. and Trojanowski , A. E. 1977 . Finding a maximum independent set . SI AM J. Comput. , 6 : 537 – 546 .
   Google Scholar
• Westbrook , J. 1992 . Proc, 19th. Int. Coll. on Automata, Lang., and Prog. . Fast incremental planarity testing . 1992 . pp. 244 – 260 .
   Google Scholar