Namespaces
Variants
Actions

Difference between revisions of "Graph, planar"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
A graph that can be regularly imbedded in the plane (cf. [[Graph imbedding|Graph imbedding]]). In other words, a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g0449901.png" /> is said to be planar if it can be represented in the plane so that various points of the plane correspond to its vertices and so that the lines corresponding to the edges of the graph do not pass through the points which correspond to the vertices (except for their terminal points) and do not mutually intersect. Problems such as the problem of colouring maps, the problem of design of communications, problems in radio-electronics which involve the realization of a circuit with the aid of planar printed subcircuits, etc., can be reduced to the study of planar graphs. Any regular (with non-intersecting edges) imbedding of a connected planar graph involves a subdivision of the plane into individual domains (faces). Such a subdivision of the plane is known as a planar map. Euler's formula
+
{{TEX|done}}
 +
A graph that can be regularly imbedded in the plane (cf. [[Graph imbedding|Graph imbedding]]). In other words, a graph $G$ is said to be planar if it can be represented in the plane so that various points of the plane correspond to its vertices and so that the lines corresponding to the edges of the graph do not pass through the points which correspond to the vertices (except for their terminal points) and do not mutually intersect. Problems such as the problem of colouring maps, the problem of design of communications, problems in radio-electronics which involve the realization of a circuit with the aid of planar printed subcircuits, etc., can be reduced to the study of planar graphs. Any regular (with non-intersecting edges) imbedding of a connected planar graph involves a subdivision of the plane into individual domains (faces). Such a subdivision of the plane is known as a planar map. Euler's formula
  
<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/g044990/g0449902.png" /></td> </tr></table>
+
$$n-m+r=2,$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g0449903.png" /> is the number of vertices, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g0449904.png" /> is the number of edges and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g0449905.png" /> is the number of faces of the map (including the exterior face) applies to any planar map. It follows that the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g0449906.png" /> (the complete graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g0449907.png" />) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g0449908.png" /> (the complete bipartite graph, cf. also [[Graph, bipartite|Graph, bipartite]]) which has three vertices in each of its parts, are not planar (Fig. a).
+
where $n$ is the number of vertices, $m$ is the number of edges and $r$ is the number of faces of the map (including the exterior face) applies to any planar map. It follows that the graph $K_5$ (the complete graph with $n=5$) and $K_{3,3}$ (the complete bipartite graph, cf. also [[Graph, bipartite|Graph, bipartite]]) which has three vertices in each of its parts, are not planar (Fig. a).
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/g044990a.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/g044990a.gif" />
Line 9: Line 10:
 
Figure: g044990a
 
Figure: g044990a
  
In a certain sense, these graphs are minimal non-planar graphs, according to the Pontryagin–Kuratowski theorem: A graph is planar if and only if it does not contain a subgraph homeomorphic to the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g0449909.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499010.png" /> (cf. [[Graph homeomorphism|Graph homeomorphism]]).
+
In a certain sense, these graphs are minimal non-planar graphs, according to the Pontryagin–Kuratowski theorem: A graph is planar if and only if it does not contain a subgraph homeomorphic to the graph $K_5$ or $K_{3,3}$ (cf. [[Graph homeomorphism|Graph homeomorphism]]).
  
There also exist other criteria of planarity (i.e. of whether or not a graph is planar). In particular, a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499011.png" /> is planar if and only if each of its non-trivial doubly-connected components has a cycle basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499012.png" /> and an additional cycle <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499013.png" /> such that any edge of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499014.png" /> is part of precisely two out of these <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499015.png" /> cycles (a cycle basis is a subset of cycles of a given graph which is independent and complete in the set of all cycles of the graph with respect to the operation of addition modulo 2, cf. [[Graph|Graph]]).
+
There also exist other criteria of planarity (i.e. of whether or not a graph is planar). In particular, a graph $G$ is planar if and only if each of its non-trivial doubly-connected components has a cycle basis $Z_1,\ldots,Z_m$ and an additional cycle $Z_0$ such that any edge of $G$ is part of precisely two out of these $m+1$ cycles (a cycle basis is a subset of cycles of a given graph which is independent and complete in the set of all cycles of the graph with respect to the operation of addition modulo 2, cf. [[Graph|Graph]]).
  
Any planar graph can be represented in the plane so that all its edges are segments of a straight line. Any triply-connected graph (cf. [[Graph, connectivity of a|Graph, connectivity of a]]) can be uniquely imbedded in the sphere (up to a homeomorphism of the sphere). Each imbedding of a planar graph in the plane, and hence each planar map, can be brought into one-to-one correspondence with its geometric dual graph, which is obtained as follows. A vertex of the planar graph is introduced into each face of the map and, if two faces have a common edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499016.png" />, the vertices they contain are joined by the edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499017.png" /> which intersects <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499018.png" /> only once (in Fig. bthe imbedding of the graph is represented by continuous lines, while the dotted lines represent its dual graph).
+
Any planar graph can be represented in the plane so that all its edges are segments of a straight line. Any triply-connected graph (cf. [[Graph, connectivity of a|Graph, connectivity of a]]) can be uniquely imbedded in the sphere (up to a homeomorphism of the sphere). Each imbedding of a planar graph in the plane, and hence each planar map, can be brought into one-to-one correspondence with its geometric dual graph, which is obtained as follows. A vertex of the planar graph is introduced into each face of the map and, if two faces have a common edge $e$, the vertices they contain are joined by the edge $e^*$ which intersects $e$ only once (in Fig. bthe imbedding of the graph is represented by continuous lines, while the dotted lines represent its dual graph).
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/g044990b.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/g044990b.gif" />
Line 19: Line 20:
 
Figure: g044990b
 
Figure: g044990b
  
A planar map each side of which is bounded by three edges is said to be a planar triangulation. The number of edges of a planar triangulation with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499019.png" /> vertices is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499020.png" />.
+
A planar map each side of which is bounded by three edges is said to be a planar triangulation. The number of edges of a planar triangulation with $n$ vertices is $3n-6$.
  
 
An intensively studied subject in the theory of graphs is the colouring of planar graphs (cf. [[Graph colouring|Graph colouring]]); for non-planar graphs one studies various numerical characteristics yielding the degree of non-planarity, including the genus, the thickness or coarseness of the graph, the number of crossings, etc. (cf. [[Graph imbedding|Graph imbedding]]).
 
An intensively studied subject in the theory of graphs is the colouring of planar graphs (cf. [[Graph colouring|Graph colouring]]); for non-planar graphs one studies various numerical characteristics yielding the degree of non-planarity, including the genus, the thickness or coarseness of the graph, the number of crossings, etc. (cf. [[Graph imbedding|Graph imbedding]]).
Line 29: Line 30:
  
 
====Comments====
 
====Comments====
A comprehensive account of planar graphs and the celebrated four-colour conjecture that every planar graph is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044990/g04499021.png" />-vertex-colourable is given by O. Ore in [[#References|[a1]]]. Recently this conjecture was proved by K. Appel and W. Haken, see [[Four-colour problem|Four-colour problem]]. For a good summary of their work see also [[#References|[a2]]].
+
A comprehensive account of planar graphs and the celebrated four-colour conjecture that every planar graph is $4$-vertex-colourable is given by O. Ore in [[#References|[a1]]]. Recently this conjecture was proved by K. Appel and W. Haken, see [[Four-colour problem|Four-colour problem]]. For a good summary of their work see also [[#References|[a2]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  O. Ore,  "The four-colour problem" , Acad. Press  (1967)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.R. Woodall,  R.J. Wilson,  "The Appel–Haken proof of the four-colour theorem"  L.W. Beineke (ed.)  R.J. Wilson (ed.) , ''Selected Topics in Graph Theory'' , Acad. Press  (1978)  pp. Chapt. 4</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.J. Wilson,  "Introduction to graph theory" , Longman  (1985)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  O. Ore,  "The four-colour problem" , Acad. Press  (1967)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.R. Woodall,  R.J. Wilson,  "The Appel–Haken proof of the four-colour theorem"  L.W. Beineke (ed.)  R.J. Wilson (ed.) , ''Selected Topics in Graph Theory'' , Acad. Press  (1978)  pp. Chapt. 4</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.J. Wilson,  "Introduction to graph theory" , Longman  (1985)</TD></TR></table>

Revision as of 19:19, 17 April 2014

A graph that can be regularly imbedded in the plane (cf. Graph imbedding). In other words, a graph $G$ is said to be planar if it can be represented in the plane so that various points of the plane correspond to its vertices and so that the lines corresponding to the edges of the graph do not pass through the points which correspond to the vertices (except for their terminal points) and do not mutually intersect. Problems such as the problem of colouring maps, the problem of design of communications, problems in radio-electronics which involve the realization of a circuit with the aid of planar printed subcircuits, etc., can be reduced to the study of planar graphs. Any regular (with non-intersecting edges) imbedding of a connected planar graph involves a subdivision of the plane into individual domains (faces). Such a subdivision of the plane is known as a planar map. Euler's formula

$$n-m+r=2,$$

where $n$ is the number of vertices, $m$ is the number of edges and $r$ is the number of faces of the map (including the exterior face) applies to any planar map. It follows that the graph $K_5$ (the complete graph with $n=5$) and $K_{3,3}$ (the complete bipartite graph, cf. also Graph, bipartite) which has three vertices in each of its parts, are not planar (Fig. a).

Figure: g044990a

In a certain sense, these graphs are minimal non-planar graphs, according to the Pontryagin–Kuratowski theorem: A graph is planar if and only if it does not contain a subgraph homeomorphic to the graph $K_5$ or $K_{3,3}$ (cf. Graph homeomorphism).

There also exist other criteria of planarity (i.e. of whether or not a graph is planar). In particular, a graph $G$ is planar if and only if each of its non-trivial doubly-connected components has a cycle basis $Z_1,\ldots,Z_m$ and an additional cycle $Z_0$ such that any edge of $G$ is part of precisely two out of these $m+1$ cycles (a cycle basis is a subset of cycles of a given graph which is independent and complete in the set of all cycles of the graph with respect to the operation of addition modulo 2, cf. Graph).

Any planar graph can be represented in the plane so that all its edges are segments of a straight line. Any triply-connected graph (cf. Graph, connectivity of a) can be uniquely imbedded in the sphere (up to a homeomorphism of the sphere). Each imbedding of a planar graph in the plane, and hence each planar map, can be brought into one-to-one correspondence with its geometric dual graph, which is obtained as follows. A vertex of the planar graph is introduced into each face of the map and, if two faces have a common edge $e$, the vertices they contain are joined by the edge $e^*$ which intersects $e$ only once (in Fig. bthe imbedding of the graph is represented by continuous lines, while the dotted lines represent its dual graph).

Figure: g044990b

A planar map each side of which is bounded by three edges is said to be a planar triangulation. The number of edges of a planar triangulation with $n$ vertices is $3n-6$.

An intensively studied subject in the theory of graphs is the colouring of planar graphs (cf. Graph colouring); for non-planar graphs one studies various numerical characteristics yielding the degree of non-planarity, including the genus, the thickness or coarseness of the graph, the number of crossings, etc. (cf. Graph imbedding).

References

[1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9


Comments

A comprehensive account of planar graphs and the celebrated four-colour conjecture that every planar graph is $4$-vertex-colourable is given by O. Ore in [a1]. Recently this conjecture was proved by K. Appel and W. Haken, see Four-colour problem. For a good summary of their work see also [a2].

References

[a1] O. Ore, "The four-colour problem" , Acad. Press (1967)
[a2] D.R. Woodall, R.J. Wilson, "The Appel–Haken proof of the four-colour theorem" L.W. Beineke (ed.) R.J. Wilson (ed.) , Selected Topics in Graph Theory , Acad. Press (1978) pp. Chapt. 4
[a3] R.J. Wilson, "Introduction to graph theory" , Longman (1985)
How to Cite This Entry:
Graph, planar. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph,_planar&oldid=17684
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article