rivin@Gang-of-Four.Stanford.EDU (Igor Rivin) (09/08/90)
Here is the promised summary of responses so far.
Thanks to all who responded.
Mike Hutton (mdhutton@theory.toronto.edu) supplied some very
interesting comments and a bibliography of work on directed graphs.
Here are his comments (the bibliography is at the end of this posting).
The ideas you stated for good representations of graphs have been
looked at. Unfortunately, the algorithms to display such things
are invariably NP-hard (these two are definitely, as are minimum
crossings, minimum area, angle ratios, ...) I think that some are
provably exponential too.
For a survey of graph drawing, you could send mail to Roberta Tamassia,
rt@cs.brown.edu. He and Peter Eades have an ongoing bibiliography
of current research.
Planar drawing is easier than general drawing -- no problems with crossing,
and much more restricted structure.
Drawing planar graphs with no symmetry requirements (as you mentioned) is
linear time -- see Chiba and Nishizeki's paper or book. They have also
studied convex drawings, and have a linear algorithm; see also
Thomassen's papers for the background graph theory.
My thesis involved drawing planar directed graphs, but it concentrates
on the testing for whether a graph can be drawn planar, and at the
same time having all edges monotonic in the y-direction (`upward'). I
have included a copy of my bibliography. In particular, you could
look at Nishiziki and Chiba's book, of the DeFrassiux Pach and Pollack
paper. I haven't been able to get at the Chrobak paper, but it claims a
linear implementation of DeFrassiux et.al.'s algorithm for drawing straight
line graphs in a small rectangular grid.
For specfic applications, more is known. Specifically, some of the
results are polynomial. Drawing Hierarchical graphs (like subroutine
charts) is linear time -- this was presented at the
Canadian Computational Geometry Conference 2 weeks ago -- I can give
you the email address of the authors if you like, but I don't have
it handy.
There is also a PhD thesis from Stanford in the mid eighties, but I
can't remember the name. Can find it if you like, I just don't have
it here. Was on graph drawing in general. There is
a nice paper by Eades on drawing graphs using 'springs' as the edges
and iterating to stabilization which worked well in practice.
Roberto Tomassia (rt@cs.brown.edu) has developed (in cooperation with
the University of Rome) tools for graph layout, and mentiones work by
a student (unnamed) at Brown that indicates that you can do pretty
good embedding (low variance in edge-lengths and angles).
Lloyd Lim (lim@iris.ucdavis.edu) has developed a "fairly efficient"
(general undirected) graph layout program for the Macintosh.
Greg Shannon (shannon@graph.cs.indiana.edu) writes that:
THis summer two of my grad students implemented the Booth and Leuker
PQ-tree planarity algorithm in Scheme. You're welcome to inspect
the code and documentation. Let me know if you're interested.
The input is an adacency list.
Also, Mark Goldberg at rpi (goldberg@turing.cs.rpi.edu) has
C program for generating an embedding from an adjacency matrix.
Ramnath Sarnath (sarnath@cs.buffalo.edu) suggests looking at Fary
embeddings of planar graphs, and refers to a paper in STOC88.
Finally, Geoffrey (Hird oravax!geoffrey@cu-arpa.cs.cornell.edu)
sent me a copy of
a posting of Lloyd Lim's containing a bibliography on graph layout,
together with enlightening comments (Lim's bibliography is
pretty much complementary to M. Hutton's bibliography). Here it is:
-----------------------------------------------------------------
The following three papers provide good surveys and/or bibliographies of graph
layout problem.
P. Eades and R. Tamassia, "Algorithms for Drawing Graphs: An Annotated
Bibliography", Technical Report #82, Department of Computer Science, University
of Queensland, Australia, 1987
R. Tamassia, G. Battista, and C. Batini, "Automatic Graph Drawing and
Readability of Diagrams", IEEE Trans. Syst., Man, Cybern., SMC-18 (1988), pp.
61-79
E.B. Messinger, "Automatic Layout of Large Directed Graphs", TR 88-07-88,
Department of Computer Science, University of Washington
The address to write to for obtaining this one is:
Dept. of Computer Science, FR-35
University of Washington
Seattle, WA 98195
This is here for the hell of it. I think it's one of the first papers on graph
drawing.
W.T. Tutte, "How to Draw a Graph", Proc. London Math Soc., v. 3 (1963), pp
743-768
I received a copy in the mail of the following paper. I don't know if it is
published or being considered for publishing at the moment. It gives O(e)
algorithms for planarity testing, planar embedding, and computing the total
number of different planar embeddings and an O(e log v) algorithm for finding
the maximal planar subgraph of the input graph. I'm not sure if these
algorithms are of practical use but they are theoretically important. The
planarity algorithm is simplified while the maximal planar subgraph algorithm
is a new result.
J. Cai, X. Han, and R.E. Tarjan, "New Solutions to Four Planar Graph Problems"
Rectilinear graph layout algorithms have been studied a lot since they are used
for VLSI layout problems. The following article describes a divide and conquer
framework using bifurcators. Layout area, crossing number, and minimax edge
length are discussed. A good reference list for VLSI papers is included. I
would say this paper is more theoretical.
S.N. Bhatt and F.T. Leighton, "A Framework for Solving VLSI Graph Layout
Problems", Journal of Computer and System Sciences, v. 28 (1984), pp. 300-343
The following paper describes a linear time alogrithm for recognizing and
embedding planar rectilinear graphs. Psuedocode is provided.
F. Hoffmann and K. Kriegel, "Embedding Rectilinear Graphs in Linear Time",
Information Processing Letters, v. 29 (1988), pp.75-79
I am most interested in drawing straight line undirected graphs. This paper is
the general algorithm I was looking for. The algorithm is very simple.
Psuedocode is provided. I'm not sure how the speed is for large graphs since I
haven't implemented it yet and the algorithm is dynamic. If anyone happens to
know the email addresses of either Tomihisa Kamada or Satoru Kawai at the
University of Tokyo, I would love to have them. I kind of like this approach.
T. Kamada and S. Kawai, "An Algorithm for Drawing General Undirected Graphs",
Information Processing Letters, v. 31 (1989), pp. 7-15
The algorithm in the following article was reported to have disappointing
performance - 13 minutes for 280 nodes on a Sun 2. I think the above algorithm
is slower since it takes 7.6 seconds for a regular dodecahedron (20 nodes) on a
VAX 8600. Using an optimistic extrapolation based on O(v**2), it comes out to
almost 25 minutes for 280 nodes on a VAX 8600.
L.A. Rowe, M. Davis, E. Messinger, C. Meyer, C. Spirakis, and A. Tuan, "A
Browser for Directed Graphs", Software Pract. Exper., v. 17 (1987), pp. 61-76
Mike Hutton's bibliography:
====================================
These mostly apply to directed, planar graphs; not planar graphs in general.
\bibitem{ahu} {\sc A.V. Aho, J.E. Hopcroft and J.D. Ullman}, ``The Design
and Analysis of Computer Algorithms", Addison-Wesley, Reading, Mass., (1974).
\bibitem{birkhoff} {\sc G. Birkhoff}, ``Lattice Theory", 3rd ed. Amer. Math.
Soc., Providence, R.I., (1967).
\bibitem{bondy-murty} {\sc J.A. Bondy and U.S.R. Murty}, ``Graph Theory with
Applications," MacMillian Co. New York, (1976).
\bibitem{booth} {\sc K.S. Booth and G.S. Lueker}, Testing the consecutive
ones property, interval graphs, and graph planarity using PQ-tree
algorithms, J.Comput.Syst.Sci. {\bf 13}, pp. 335-379 (1976).
\bibitem{chiba-convex} {\sc N. Chiba, T. Yamanouchi and T. Nishizeki},
Linear algorithms for convex drawings of planar graphs, in
{\em Progress in Graph Theory} (J.A. Bondy and U.S.R. Murty eds.)
Academic Press, New York. pp. 153-173 (1984).
\bibitem{chiba-draw} {\sc N. Chiba, T. Nishizeki, S. Abe and T. Ozawa},
A linear algorithms for embedding planar graphs using PQ-trees,
{\em J.Comput.Syst.Sci.} {\bf 30,1}, pp. 54-76 (1985).
\bibitem{chrobak} {\sc M. Chrobak}. A Linear-Time Algorithm for Drawing
a Planar Graph on a Grid", Manuscript, Univ.Calif.Riverside, (1988)
\bibitem{defray} {\sc H. DeFraysseix, J. Pach, and R. Pollack}.
Small Sets Supporting Fary Embeddings of Planar Graphs,
{\em Proc. 20'th Annual Symposium on the Theory of Computing},
pp. 426-433 (1988).
\bibitem{dibattista-draw} {\sc G. DiBattista and R. Tomassia}. Algorithms
for plane representations of acyclic digraphs, {\em Theoretical
Computer Science} {\bf 61}, pp. 175-178 (1988).
\bibitem{dibattista-hier} {\sc G. DiBattista and E. Nardelli}. An algorithm
for testing planarity of hierarichical graphs, in {\em Graph-Theoretic
Concepts in Computer Science}, Lecture Notes in Computer Science {\bf 246}
(Springer, Berlin), pp. 277-289, (1987).
\bibitem{dibattista-symmetry} {\sc G. DiBattista, R. Tomassia and I.G. Tollis}.
Area Requirement and Symmetry Display in Drawing Graphs,
Proc. ACM Symposium on Computational Geometry, pp. 51-60, (1989).
\bibitem{even} {\sc S. Even}. {\em Graph Algorithms}, Computer Science
Press, Rockville, Maryland. (1979).
\bibitem{even-tarjan} {\sc S. Even and R. Tarjan}. Computing an st-numbering,
Theoretical Computer Science {\bf 2}, pp. 339-344 (1976).
Press, Rockville, Maryland. (1979).
\bibitem{fary} {\sc I. F\'{a}ry}. On straight line representing of planar
graphs. {\em Acta. Sci. Math. (Szeged)} {\bf 11}, pp. 319-321 (1948).
\bibitem{hopcroft-tarjan} {\sc J. Hopcroft and R. Tarjan,} Efficient
planarity testing {\em J.ACM} {\bf 21,4}, pp. 549-568 (1974).
\bibitem{triconnected} {\sc H. Hopcroft and R.E. Tarjan}, Dividing a graph
into triconnected components, {\em SIAM J. Comput. 2}, pp. 135-158 (1972).
\bibitem{kelly} {\sc D. Kelly}, Fundamentals of planar ordered sets,
{\em Discrete Math {\bf 63}}, pp. 197-216 (1987).
\bibitem{kelly-rival} {\sc D. Kelly and I. Rival}, Planar Lattices,
{\em Can. J. Math., Vol XXVII, No. 3}, pp. 636-665 (1975).
\bibitem{mike} {\sc M.D. Hutton,} Upward Planar Drawing of Single
Source Acyclic Digraphs. Masters Thesis, University of Waterloo (Sept. 1990).
\bibitem{lempel} {\sc A. Lempel, S. Even, and I. Cederbaum}, An Algorithm
for Planarity Testing of Graphs, in {\em Theory of Graphs, International
Symposium, Rome}, P. Rosenstiehl, Ed., Gordon and Breach, N.Y. pp. 215-232
(1967).
\bibitem{nishizeki} {\sc T. Nishizeki and N. Chiba}, ``Planar Graphs: Theory
and Algorithms," Annals of Discrete Mathematics 32, Elsevier Science
Publishing Company, Inc. New York, (1988).
\bibitem{platt} {\sc C.R. Platt}, Planar Lattices and Planar Graphs,
{\em J. Comb. Theory (B) {\bf 21}}, pp. 30-39 (1976).
\bibitem{platt} {\sc R. Read}, New Methods for Drawing a Planar Graph
Given the Cyclic order,
{\em Congressus Numerantium} Vol. 56, pp. 31-44 (1976).
\bibitem{schnyder} {\sc W. Schnyder}, Embeding Planar Graphs on the Grid,
{\em Proc. First ACM-SIAM Symposium on Discrete Algorithms}, pp. 138-148 (1990).
\bibitem{tarjan} {\sc R.E. Tarjan}, Depth-first search and linear graph
algorithms, {\em SIAM J. Comput. 1,2}, pp. 146-159 (1972).
\bibitem{annbib} {\sc R. Tamassia and P. Eades}, Algorithms for Drawing
Graphs: an Annotated Bibliography, Brown University TR CS-89-09 (1989).
\bibitem{thomassen} {\sc C. Thomassen}, Planar acyclic oriented graphs.
{\em Order {\bf 5}}, pp. 349-361 (1987).
\bibitem{other-thomassen} {\sc C. Thomassen}, Planarity and duality of finite
and Infinite Graphs, {\em J. Combin. Theory {\bf B29}}, pp. 244-271 (1980).
\bibitem{trotter} {\sc W.T. Trotter}, Graphs and partially ordered sets, in
{\em Selected Topics in Graph Theory 2} (L.W. Beineke and R.J. Wilson,
editors), Academic Press, New York. pp. 237-268 (1983).
\bibitem{tutte-convex} {\sc W.T. Tutte}, Convex representations of graphs,
{\em Proc. London Math. Soc.} Vol.10, pp. 304-320 (1960).
\bibitem{tutte-draw} {\sc W.T. Tutte}, How to Draw a Graph,
{\em Proc. London Math. Soc.} Vol.3, No.13, pp. 743-768 (1963).
--
Igor Rivin Wolfram Research, Inc.
rivin@Gang-of-Four.Stanford.EDU or
rivin@wri.com