Namespaces
Variants
Actions

Difference between revisions of "Graph imbedding"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g0449401.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g0449402.png" /> (cf. [[Graph, planar|Graph, planar]], Figure 1). The smallest genus of the two-dimensional orientable surface in which a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g0449403.png" /> can be regularly imbedded is said to be the genus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g0449404.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g0449405.png" />. It has been proved, in particular, that
+
<!--
 +
g0449401.png
 +
$#A+1 = 22 n = 0
 +
$#C+1 = 22 : ~/encyclopedia/old_files/data/G044/G.0404940 Graph imbedding
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g0449406.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g0449407.png" /> is the complete graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g0449408.png" /> vertices and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g0449409.png" /> is the least integer not smaller than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494010.png" />;
+
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|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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494011.png" /></td> </tr></table>
+
$$
 +
\gamma ( K _ {n} )  = \
 +
\left ]
 +
\frac{( n - 3) ( n - 4) }{12}
 +
\right [ ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494012.png" /> is the complete bipartite graph (cf. [[Graph, bipartite|Graph, bipartite]]);
+
where $  K _ {n} $
 +
is the complete graph with  $  n $
 +
vertices and  $  \left ] a \right [ $
 +
is the least integer not smaller than  $  a $;
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494013.png" /></td> </tr></table>
+
$$
 +
\gamma ( K _ {m, n }  )  = \
 +
\left ]
 +
\frac{( m - 2) ( n - 2) }{4}
 +
\right [ ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494014.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494015.png" />-dimensional cube. The thickness <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494016.png" /> of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494017.png" /> is the smallest number of its planar subgraphs whose union yields <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494018.png" />. It has been proved, in particular, that
+
where $  K _ {m, n }  $
 +
is the complete bipartite graph (cf. [[Graph, bipartite|Graph, bipartite]]);
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494019.png" /></td> </tr></table>
+
$$
 +
\gamma ( Q _ {n} )  = \
 +
1 + ( n - 4) \cdot
 +
2 ^ {n - 3 } ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494020.png" /></td> </tr></table>
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494021.png" /></td> </tr></table>
+
$$
 +
\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).
 
(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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044940/g04494022.png" />-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.
+
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.
 
Problems involving graph imbedding in surfaces and in lattices occur in automatic computer design, communication design, etc.
Line 27: Line 84:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> , ''Graph theory. Coverings, imbeddings, tournaments'' , Moscow  (1974)  pp. 82–159  (In Russian; translated from English, French and German)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> , ''Graph theory. Coverings, imbeddings, tournaments'' , Moscow  (1974)  pp. 82–159  (In Russian; translated from English, French and German)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Latest revision as of 19:42, 5 June 2020


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)
How to Cite This Entry:
Graph imbedding. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph_imbedding&oldid=47128
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article