Graph Embedding

A graph embedding in a surface represents distinct vertices by distinct points and edges by simple arcs whose only intersections are common endpoints. Requiring all intersections to occur at common endpoints distinguishes an embedding from a general graph drawing, which may have crossings. Specifying the surface gives such notions as a planar graph embedding, torus graph embedding, or projective plane graph embedding.

In geometric and computational settings, the word embedding also occurs in the names of drawings or layouts that satisfy particular geometric conditions. A unit-distance embedding, for example, constrains edge lengths without requiring the edges to be disjoint. The terms circular drawing, integral drawing, and straight line drawing describe the corresponding layouts without implying the topological intersection condition. Such drawings can be made in the plane or in three or more dimensions, as illustrated above for the cubical graph.

The underlying graph represented by a drawing or embedding is considered independently of that representation.

A good choice of drawing can lead to particularly illuminating diagrams. For example, the circular drawing (left) of the cubical graph illustrates this graph's inherent symmetries.

Skiena (1990) considers a number of different types of drawings, including circular drawings, ranked, radial, rooted, and spring. Graphs 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. Drawings of trees can be visualized using TreePlot[g].

Hong and Eades (2003) gave a linear time algorithm for drawing disconnected planar graphs with maximum number of symmetries. Freivalds et al. (2002) gave an algorithm for drawing disconnected graphs based on polyomino packing.

Precomputed drawings of certain types for a number of graphs are available in the Wolfram Language as GraphData[g, "Graph", type].