A simulated annealing algorithm for the maximum planar subgraph problem. (English) Zbl 1055.05144
Given a graph \(G=(V,E)\) without loops and parallel edges, its subgraph \(G'=(V,E')\) is called a maximum planar subgraph if it is planar and the cardinality of \(E'\) is maximal among all planar subgraphs of \(G\). The author gives a new heuristic algorithm for finding maximum planar subgraphs of a graph. It is based on the simulated annealing optimization scheme and needs an implementation of the planarity test. Experimental results show that it outperforms earlier heuristics; it is faster and its solution quality is better.
Reviewer: Ján Plesník (Bratislava)
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
DIMACSReferences:
| [1] | DOI: 10.1007/BF02086607 · Zbl 0854.68073 · doi:10.1007/BF02086607 |
| [2] | Di Battista G., Graph Drawing (1999) |
| [3] | DOI: 10.1111/j.1475-3995.1995.tb00007.x · Zbl 0868.90072 · doi:10.1111/j.1475-3995.1995.tb00007.x |
| [4] | Liebers A., J. Graph Algorithms Appl. 5 pp 1– (2001) |
| [5] | Vrtó I. (2003) Crossing numbers of graphs: A bibliography Available electronically atftp://ifi.savba.sk/pub/imrich/crobib.ps.gz |
| [6] | Harary F., Graph Theory (1971) |
| [7] | DOI: 10.1007/PL00007219 · Zbl 0896.05020 · doi:10.1007/PL00007219 |
| [8] | DOI: 10.1016/0095-8956(91)90100-X · Zbl 0675.05042 · doi:10.1016/0095-8956(91)90100-X |
| [9] | Liu P., Proc. 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing pp 727– (1977) |
| [10] | Yannakakis M., Proc. 10th Annual ACM Symposium on Theory of Computing pp . 253–264– (1978) |
| [11] | DOI: 10.1016/S0022-0000(76)80045-1 · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1 |
| [12] | DOI: 10.1145/321850.321852 · Zbl 0307.68025 · doi:10.1145/321850.321852 |
| [13] | Boyer J., Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms pp 140– (1999) |
| [14] | DOI: 10.1016/S0304-3975(98)00120-0 · Zbl 0930.05092 · doi:10.1016/S0304-3975(98)00120-0 |
| [15] | Cimikowski R., J. Inf. Opt. Science 18 pp 49– (1997) |
| [16] | DOI: 10.1016/0012-365X(94)00326-E · Zbl 0845.05032 · doi:10.1016/0012-365X(94)00326-E |
| [17] | Cimikowski R., Proc. of the 23rd Southeastern Internation Conference on Combinatorics, Graph Theory, and Computing pp 21– (1992) |
| [18] | Cimikowski R., Proc. of the 6th ACM-SIAM Symposium on Discrete Algorithms pp 322– (1995) |
| [19] | DOI: 10.1006/jagm.1997.0920 · Zbl 0919.68093 · doi:10.1006/jagm.1997.0920 |
| [20] | DOI: 10.1080/00207169408804320 · Zbl 0842.68057 · doi:10.1080/00207169408804320 |
| [21] | DOI: 10.1016/0020-0255(95)00011-D · doi:10.1016/0020-0255(95)00011-D |
| [22] | Aragon C. R., Oper. Res. 3 pp 378– (1991) |
| [23] | DOI: 10.1287/opre.37.6.865 · Zbl 0698.90065 · doi:10.1287/opre.37.6.865 |
| [24] | Reeves C., Modern Heuristic Techniques for Combinatorial Problems (1995) · Zbl 0942.90500 |
| [25] | DOI: 10.1002/net.3230240203 · Zbl 0789.90083 · doi:10.1002/net.3230240203 |
| [26] | DOI: 10.1126/science.245.4923.1221 · doi:10.1126/science.245.4923.1221 |
| [27] | DOI: 10.1002/(SICI)1097-0037(199705)29:3<173::AID-NET5>3.0.CO;2-E · Zbl 0885.90112 · doi:10.1002/(SICI)1097-0037(199705)29:3<173::AID-NET5>3.0.CO;2-E |
| [28] | Pitsoulis L., Handbook of Applied Optimization pp pp. 168–183– (2002) |
| [29] | DOI: 10.1109/43.31548 · doi:10.1109/43.31548 |
| [30] | DOI: 10.1063/1.1699114 · doi:10.1063/1.1699114 |
| [31] | van Laarhoven P., Simulated Annealing: Theory and Applications (1987) · doi:10.1007/978-94-015-7744-1 |
| [32] | Aarts E., Local Search in Combinatorial Optimization (1997) · Zbl 0869.00019 |
| [33] | LEDA version 4.3 (commercial) (2002) Available athttp://www.algorithmic-solutions.com |
| [34] | Johnson D., Proc. of the 5th and 6th DIMACS Implementation Challenges pp 215– (2002) |
| [35] | Mutzel P. (1994) The Maximum Planar Subgraph Problem PhD thesis Universität zu Köln |
| [36] | DOI: 10.1145/300515.300517 · Zbl 1064.05502 · doi:10.1145/300515.300517 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
