chrise@bcsaic.UUCP (Chris Esposito) (11/10/88)
LINE EATER FODDER Several people have written in asking about graph drawing algorithms, especially those that minimize edge crossings. For planar graphs, this is easy and fast; there are linear-time (in the number of nodes) algorithms for planar graph embedding (drawing with no edge crossings) that have been developed by Booth and Lueker, and by Hopcroft and Tarjan - see the references below for more details. For trees it is also obviously easy to do. In the general case, the answer is not so hopeful. The `crossing number' of a graph G, denoted v(G), is the minimum number of edge crossings when G is drawn in the plane. Garey and Johnson have shown that the general crossing number decision problem "given an arbitrary graph G, and an integer k, is v(G) <= k?" is NP-complete, and so is probably intractable. As a consequence, much of the recent research has concentrated either on finding upper and lower bounds for crossing numbers, or on finding exact values for special graphs. References on graph drawing 1. S. BHATT AND F. LEIGHTON, A framework for solving VLSI graph layout problems, J. Comput. System Sci. 28, (1984) 300-343. 2. K. S. BOOTH AND G. S. LUEKER, Testing the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci. (1976) 335-379. 3. N. CHIBA, T. NISHIZEKI, S. ABE, AND T. OZAWA, A linear algorithm for embedding planar graphs using PQ-trees, J. Comput. and System Sci., (1985) 54-76. 4. D. DEARHOLT, R. SCHVANEVELDT, AND F. DURSO, Properties of networks derived from proximities. MCCS-85-14, Computing Research Laboratory, New Mexico State University, (1985). 5. P. EADES, A heuristic for graph drawing, unpublished manuscript (1984). 6. P. EADES AND N. WORMALD, An NP-hard graph drawing problem. Technical Report 52, Department of Computer Science, University of Queensland (1984). 7. C. ESPOSITO, Graph graphics: theory and practice, Computers and Mathematics, Vol 15, #4, 1988. 8. S. EVEN AND R. TARJAN, Computing an st-numbering Theor. Comput. Sci. (1976) 339-344. 9. M. R. GAREY AND D. S. JOHNSON, Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods (1983) 312-316. 10. A. J. GOLDSTEIN, An efficient and constructive algorithm for testing whether a graph can be embedded in a plane, Proceedings of the Graph and Combinatorics Conference, Office of Naval Research Logistics Proj., Department of Mathematics, Princeton University (1963). 11. F. HARARY, Graph Theory, Addison-Wesley, Reading. (1969). 12. J. E. HOPCROFT AND R. E. TARJAN, Efficient planarity testing, J. ACM (1974) 549-568. 13. C. E. LEISERSON, Area-efficient Layouts for VLSI. Twenty-First Annual Symposium on Foundations of Computer Science,IEEE, New York (1980). 14. A. LEMPEL, S. EVEN, AND I. CEDERBAUM, An algorithm for planarity testing of graphs. Theory of Graphs, (P. Rosenstiel, Ed.) Gordon & Breach, New York (1967) 215-232. 15. R. J. LIPTON AND R. E. TARJAN, Applications of a planar seperator theorem, unpublished manuscript (1977). 16. Z. MILLER AND J. B. ORLIN, NP-completeness for minimizing maximum edge length in grid embeddings, J. Algorithms (1985) 10-16. 17. R. C. Read, A survey of graph graphics. Proc. Indiana Conf. on Graph Theory, to appear. 18 R. W. SHIREY, Implementation and analysis of efficient graph planarity testing algorithms, Doctoral Thesis, University of Wisconsin (1969). 19. W. T. TUTTE, How to draw a graph. Proc. London Math. Soc. (1963) 743-768. 20. J. ULLMAN, Computational Aspects of VLSI, Computer Science Press, Rockville (1984). -- ------------------------------------------------------------------------ "what if we can't tell the difference between AI and artificial stupidity? Chris Esposito | CSNET: chrise@boeing.com Boeing Advanced Technology Center | uucp: ...!uw-beaver!ssc-vax!bcsaic!chrise