Algorithm 797: Fortran subroutines for approximate solution of graph planarization problems using GRASP

ABSTRACT

We describe Fortran subroutines for finding approximate solutions of the maximum planar subgraph problem (graph planarization) using a Greedy Randomized Adaptive Search Procedure (GRASP). The design and implementation of the code are described in detail. Computational results with the subroutines illustrate the quality of solutions found as a function of number of GRASP iterations.

REFERENCES

• 1: Jiazhen Cai , Xiaofeng Han , Robert E. Tarjan, An O(m log n)-time algorithm for the maximal planar subgraph problem, SIAM Journal on Computing, v.22 n.6, p.1142-1162, Dec. 1993 [doi>10.1137/0222068]
• 2: DI BATTISTA,G.AND TAMASSIA, R. 1989. Incremental planarity testing. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS '89, Research Triangle Park, NC, Oct. 30-Nov. 1) IEEE Computer Society Press, Los Alamitos, CA, 436-441.
• 3: FEO,T.AND RESENDE, M. 1995. Greedy randomized adaptive search procedures. J. Global Optim. 6, 109-133.
• 4: GAVRIL, F. 1973. Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3, 261-273.
• 5: GOLDSCHMIDT,O.AND TAKVORIAN, A. 1994. An efficient graph planarization two-phase heuristic. Networks 24, 69-73.
• 6: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland, 2004
• 7: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 8: JAYAKUMAR, R., THULASIRAMAN, K., AND SWAMI, N. 1989. O~n 2 ! algorithms for graph planarization. IEEE Trans. Comput.-Aided Des. 8, 257-267.
• 9: J~NGER,M.AND MUTZEL, P. 1996. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica 16, 33-59.
• 10: LEMPEL, A., EVEN, S., AND CEDARBAUM, I. 1966. An algorithm for planarity testing of graphs. In Proceedings of the International Symposium on Theory of Graphs (Rome) Gordon and Breach Science Publishers, Inc., Langhorn, PA, 215-232.
• 11: LIU,P.AND GELDMACHER, R. 1977. On the deletion of nonplanar edges of a graph. In Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL) 727-738.
• 12: RESENDE,M.G.C.AND RIBEIRO, C. C. 1997. A GRASP for graph planarization. Networks 29, 173-189.
• 13: SARRAFZADEH,M.AND LEE, D. 1989. A new approach to topological via minimization. IEEE Trans. Comput.-Aided Des. 8, 890-900.
• 14: TAKEFUJI,Y.AND LEE, K. 1989. A near-optimum parallel planarization algorithm. Science 245, 1221-1223.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN 77

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Performance

Keywords:
GRASP, automatic graph drawing, combinatorial optimization, graph planarization, local search