A graph embedding, sometimes also called a graph drawing, is a particular drawing of a graph. Graph embeddings are most commonly drawn in
the plane, but may also be constructed in three or more dimensions. The above figure
shows several embeddings of the cubical graph. The
most commonly encountered graph embeddings are generally straight
line embeddings, in which all edges are drawn as straight line segments.
A good choice of embedding can lead to particularly illuminating diagrams. For example, the circular (left) embedding of the cubical graph
illustrates this graph's inherent symmetries.
Skiena (1990) considers a number of different types of embeddings, including circular, ranked, radial, rooted, and spring. Graph embeddings can be visualized in the Wolfram Language in two dimensions using
the option GraphLayout.
Alternately, GraphPlot[g]
can be used in two dimensions and GraphPlot3D[g]
in three dimensions. Embeddings for trees can be visualized using TreePlot[g].
Hong and Eades (2003) gave a linear time algorithm for drawing disconnectedplanar graphs with maximum number of symmetries. Freivalds
et al. (2002) gave an algorithm for embedding disconnected
graphs based on polyomino packing.
Precomputed embeddings of certain types for a number of graphs are available in the Wolfram Language as GraphData[g,
"Graph", type].
Chung, F.; Leighton, T.; and Rosenberg, A. "Embeddings Graphs in Books: A Layout Problem with Applications to VLSI Design." SIAM
J. Algebraic Disc. Meth.8, 33-58, 1987.Di Battista, G.;
Eades, P.; Tamassia, R.; and Tollis, I. G. Graph
Drawing: Algorithms for the Visualization of Graphs. Englewood Cliffs, NJ:
Prentice-Hall, 1998.Di Battista, G.; Garg, A.; Liotta, G.; Tamassia,
R.; Tassinari, E.; and Vargiu, F. "An Experimental Comparison of Four Graph
Drawing Algorithms." Computational Geom.7, 303-325, 1997.Eades,
P. "A Heuristic for Graph Drawing." Congr. Numer.42, 149-160,
1984.Eades, P.; Fogg, I.; and Kelly, D. SPREMB:
A System for Developing Graph Algorithms. Technical Report. Department of
Computer Science. St. Lucia, Queensland, Australia: University of Queensland,
1988.Eades, P. and Tamassia, R. "Algorithms for Drawing Graphs:
An Annotated Bibliography." Technical Report CS-89-09. Department of Computer
Science. Providence, RI: Brown University, Feb. 1989.Freivalds,
K.; Dogrusoz, U.; and Kikusts, P. "Disconnected Graph Layout and the Polyomino
Packing Approach." In Graph
Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23-26, 2001,
Revised Papers (Ed. P. Mutzel, M. Jünger, and S. Leipert).
Berlin: Springer, pp. 378-391, 2002.Hong, S.-H. and Eades, P. "Symmetric
Layout of Disconnected Graphs." In Algorithms
and Computation: 14th International Symposium, ISAAC 2003, Kyoto, Japan, December
15-17, 2003, Proceedings (Ed. T. Ibaraki, N. Katoh, and H. Ono).
Berlin: Springer, pp. 405-414, 2003.Kamada, T. and Kawai, S. "An
Algorithm for Drawing General Undirected Graphs." Inform. Processing Lett.31,
7-15, 1989.Malitz, S. M. "Genus g Graphs Have Pagenumber
." In Proc. 29th Sympos.
Found. Computer Sci. IEEE Press, pp. 458-468, 1988.Pemmaraju,
S. and Skiena, S. Computational
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge,
England: Cambridge University Press, 2003.Reingold, E. and Tilford,
J. "Tidier Drawings of Trees." IEEE Trans. Software Engin.7,
223-228, 1981.Skiena, S. "Graph Embeddings." §3.3 in
Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 81 and 98-118, 1990.Supowit, K. and Reingold,
E. "The Complexity of Drawing Trees Nicely." Acta. Inform.18,
377-392, 1983.Tamassia, R. "Graph Drawing." Ch. 21 in
Handbook
of Computational Geometry (Ed. J.-R. Sack and J. Urrutia). Amsterdam,
Netherlands: North-Holland, pp. 937-971, 2000.Vaucher, J. "Pretty
Printing of Trees." Software Pract. Experience10, 553-561, 1980.Wetherell,
C. and Shannon, A. "Tidy Drawings of Trees." IEEE Trans. Software Engin.5,
514-520, 1979.White, A. T. "Imbedding Problems in Graph Theory."
Ch. 6 in Graphs of Groups on Surfaces: Interactions and Models (Ed. A. T. White).
Amsterdam, Netherlands: Elsevier, pp. 49-72, 2001.
." In Proc. 29th Sympos.
Found. Computer Sci. IEEE Press, pp. 458-468, 1988.Pemmaraju,
S. and Skiena, S.