Randomized graph drawing with heavy-duty preprocessing

ABSTRACT

We present a graph drawing system for general undirected graphs with straight-line edges. It carries out a rather complex set of preprocessing steps, designed to produce a topologically good, but not necessarily nice-looking layout, which is then subjected to Davidson and Harel's simulated annealing beautification algorithm. The intermediate layout is planar for planar graphs and attempts to come close to planar for nonplanar graphs. The system's results are significantly better, and much faster, than what the annealing approach is able to achieve on its own.

REFERENCES

• BETT93: Di Battista, G., P. Eades, R. Tammassia and I. G. Tollis, "Algorithms fcr Automatic Graph Drawing: An Annotated Bibliography", Technical Report, Dept. of Computer Science, Brown IJniversity, Providence, 1993.
• Ber73: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• BL76: Booth, K.S. and G.S. Lueker, "Testing for the Consecutive Ones Property, Interval Graphs, ant1 Graph Planarity Using PQ- tree Algorithms", J. Comput. Syst. Sci. 13 (1976), 335-879.
• CNAO85: Norishige Chiba , Takao Nishizeki , Shigenobu Abe , Takao Ozawa, A linear algorithm for embedding planar graphs using PQ-trees, Journal of Computer and System Sciences, v.30 n.1, p.54-76, Feb. 1985 [doi>10.1016/0022-0000(85)90004-2]
• CP90: Chrobak, M. and T.H. Payne, "A Linear Time Algorithm for Drawing a F'lanar Graph on a Grid", Technical Report IJCR-CSS-90-2, Dept. of Math. and Camp. Science, IJniversity of California, Riverside, CA, 1990.
• DH89: Davidson R. and D. Harel, "Drawing Graphs Nicely Using Simulated Annealing", Technical report, The Weizmann Institute of Science, Rehovot, Israel, 1989; revised 1992, 1993; Comm. Assoc. Gomput. Mach., to appear.
• Ead84: Eades, P., "A Heuristic for Graph Drawing", Gong. Nurner 42 (1984), 149-160.
• FPP88: Hubert de Fraysseix , János Pach , Richard Pollack, Small sets supporting fary embeddings of planar graphs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.426-433, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62254]
• Har88: David Harel, On visual formalisms, Communications of the ACM, v.31 n.5, p.514-530, May 1988 [doi>10.1145/42411.42414]
• HS93: Harel, D. and M. Sardas, "An Incremental Drawing Algorithm for Planar Graphs", in preparation.
• JTS89: Jayakumar, R., K. Thulasiraman and M.N.S. Swamy, "O(n') Algorithm for Graph Planarization" , IEEE Trans. on Computer-Aided Design 83 (1989), 257- 267.
• KK89: T. Kamada , S. Kawai, An algorithm for drawing general undirected graphs, Information Processing Letters, v.31 n.1, p.7-15, April 1989 [doi>10.1016/0020-0190(89)90102-6]
• Kan92: Kant, G., "An O(n') Maximal Planarization Algorithm Rased on PQ-trees" , Technical Report RUU-CS-92-03, Dept. of C:omputer Science, IJtrecht IJniversity, The Netherlands, 1992.
• LA87: P. J. M. Laarhoven , E. H. L. Aarts, Simulated annealing: theory and applications, Kluwer Academic Publishers, Norwell, MA, 1987
• LEC67: Lempel, A., S. Even and I. Gderbaum, "An Algorithm for Planarity Testing of Graphs", In Theory of Graphs: International Symposiutn (P. Rosenstiehl, Ed.), Gordon and Rreach, New York, 1967, pp. 215-232.
• Rea87: Read, R.C:., "A New Method for Drawing a Planar Graph Given the Order of Edges at Each Vertex", Gong. Nutner. 56 (1987), 31-44.
• Sar93: Sardas, M ., "Drawing Graphs Nicely on the Plane", M.Sc. Thesis, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel, 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design