Graph imbedding

A mapping of the vertices and edges of a graph into points and continuous curves of a given space, respectively, such that the vertices incident to an edge are mapped to the end points of the curve corresponding to this edge. A regular imbedding is an imbedding in which different points correspond to different vertices while curves corresponding to edges do not pass (except for their terminal points) through points corresponding to the vertices and do not intersect. Any graph can be regularly imbedded in three-dimensional space. A graph that can be regularly imbedded in a plane is said to be planar. There exist non-planar graphs, such as the graphs $ K _ {5} $ and $ K _ {3,3 } $( cf. Graph, planar, Figure 1). The smallest genus of the two-dimensional orientable surface in which a graph $ G $ can be regularly imbedded is said to be the genus $ \gamma ( G) $ of $ G $. It has been proved, in particular, that

$$ \gamma ( K _ {n} ) = \ \left ] \frac{( n - 3) ( n - 4) }{12} \right [ , $$

where $ K _ {n} $ is the complete graph with $ n $ vertices and $ \left ] a \right [ $ is the least integer not smaller than $ a $;

$$ \gamma ( K _ {m, n } ) = \ \left ] \frac{( m - 2) ( n - 2) }{4} \right [ , $$

where $ K _ {m, n } $ is the complete bipartite graph (cf. Graph, bipartite);

$$ \gamma ( Q _ {n} ) = \ 1 + ( n - 4) \cdot 2 ^ {n - 3 } , $$

where $ Q _ {n} $ is the $ n $- dimensional cube. The thickness $ \theta ( G) $ of a graph $ G $ is the smallest number of its planar subgraphs whose union yields $ G $. It has been proved, in particular, that

$$ \theta ( K _ {p} ) = \ \left [ \frac{p + 7 }{6} \right ] \ \textrm{ if } p \neq 9, 10; \ \ \theta ( K _ {9} ) = \theta ( K _ {10} ) = 3, $$

$$ \theta ( Q _ {n} ) = \left ] \frac{n + 1 }{4} \right [ , $$

$$ \theta ( K _ {m, n } ) = \left ] \frac{mn}{2 ( m + n - 2) } \right [ $$

(possibly with some exceptions).

Other numerical characteristics connected with graph imbeddings have also been studied. These include, for example, the number of crossings — the smallest number of intersections of edges sufficient to imbed a given graph in a given surface; the coarseness — the largest number of non-planar subgraphs in a given graph which do not have common edges, etc. Imbeddings in non-orientable surfaces have also been considered. An imbedding of a graph in an $ n $- dimensional integral lattice is a mapping into the lattice under which the vertices are mapped to different nodes of the lattice, while the edges follow the lattice lines.

Problems involving graph imbedding in surfaces and in lattices occur in automatic computer design, communication design, etc.

References

[1]	F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[2]	, Graph theory. Coverings, imbeddings, tournaments , Moscow (1974) pp. 82–159 (In Russian; translated from English, French and German)

Comments

For a recent survey of the parameters discussed here see [a1] and [a2]. Two important related references are [a3] and [a4].

References

[a1]	A.T. White, L.W. Beineke, "Topological graph theory" L.W. Beineke (ed.) R.J. Wilson (ed.) , Selected topics in graph theory , Acad. Press (1978) pp. Chapt. 2
[a2]	A.T. White, "The proof of the Heawood conjecture" L.W. Beineke (ed.) R.J. Wilson (ed.) , Selected topics in graph theory , Acad. Press (1978) pp. Chapt. 3
[a3]	A.T. White, "Graphs, groups and surfaces" , North-Holland (1973)
[a4]	G. Ringel, "Map colour theorem" , Springer (1974)