In graph theory, a planar graph is a graph that can be embedded in a plane (mathematics) so that no Edge_(graph_theory)s intersect. For example, the following two graphs are planar: (the second one can be redrawn without intersecting edges by moving one of the diagonal edges to the outside), while the two graphs shown below are ''not'' planar:
It is not possible to redraw these without edge intersections. In fact, these two are the smallest non-planar graphs, a consequence of the characterization below. == Kuratowski's theorem == The Poland mathematician Kazimierz Kuratowski provided a characterization of planar graphs, now known as '''Kuratowski's theorem''': :A finite graph is planar if and only if it does not contain a subgraph that is an ''expansion'' of ''K''5 (the complete graph on 5 vertices) or ''K''3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three). An ''expansion'' of a graph results from inserting vertices into edges, i.e. changing an edge * --- * to * --- * --- *, and repeating this zero or more times. Equivalent formulations of this theorem, also known as "Theorem P" include :A finite graph is planar if and only if it does not contain a subgraph that is homeomorphism (graph theory) to ''K''5 or ''K''3,3. and :A finite graph is planar if and only if it does not have ''K''5 or ''K''3,3 as a minor (graph theory). A far-reaching generalization of Kuratowski's theorem is given by the Robertson-Seymour theorem; in the language of this theorem, ''K''5 and ''K''3,3 are the "forbidden minors" for the class of finite planar graphs. == Other planarity criteria == In practice, it is difficult to use Kuratowski's criterion to quickly decide whether a given graph is planar. However, there exist fast algorithms for this problem: for a graph with ''n'' vertices, it is possible to determine in time Big O notation(''n'') whether the graph is planar or not. For a simple, connected, planar graph with ''n'' vertices and ''e'' edges: : Theorem 1. If ''n'' ≥ 3 then ''e'' ≤ 3''n'' - 6 : Theorem 2. If ''n'' > 3 and there are no cycles of length 3, then ''e'' ≤ 2''n'' - 4 Note that these theorems are if, not if and only if, and therefore can only be used to prove a graph is not planar, not that it is planar. If both theorem 1 and 2 fail, Theorem P must be used. The graph ''K''3,3 has 6 vertices, 9 edges, and no cycles of length 3. Therefore, by Theorem 2, it is not planar. For two planar graphs with ''n'' vertices, it is possible to determine in time O(''n'') whether they are graph theory or not. MacLane's planarity criterion gives an algebraic characterization of finite planar graphs, via their cycle spaces. === Euler's formula === '''Euler's formula''' states that if a finite graph theory planar graph is drawn in the plane without any edge intersections, and ''v'' is the number of vertices, ''e'' is the number of edges and ''f'' is the number of faces (regions bounded by edges, including the outer infinitely large region), then :''v'' − ''e'' + ''f'' = 2, i.e. the Euler characteristic is 2. As an illustration, in the first planar graph given above, we have ''v''=6, ''e''=7 and ''f''=3. If the second graph is redrawn without edge intersections, we get ''v''=4, ''e''=6 and ''f''=4. Euler's formula can be proven as follows: if the graph isn't a tree (graph theory), then remove an edge which completes a cycle. This lowers both ''e'' and ''f'' by one, leaving ''v'' − ''e'' + ''f'' constant. Repeat until you arrive at a tree; trees have ''v'' = ''e'' + 1 and ''f'' = 1, yielding ''v'' - ''e'' + ''f'' = 2. In a finite connected ''simple'' planar graph, any face (except possibly the outer one) is bounded by at least three edges and every edge touches at most two faces; using Euler's formula, one can then show that these graphs are ''sparse'' in the sense that ''e'' ≤ 3''v'' - 6 if ''v'' ≥ 3. A simple graph is called maximal planar if it is planar but adding any edge would destroy that property. All faces (even the outer one) are then bounded by three edges, explaining the alternative term triangular for these graphs. If a triangular graph has ''v'' vertices with ''v'' > 2, then it has precisely 3''v''-6 edges and 2''v''-4 faces. Note that Euler's formula is also valid for simple polyhedron. This is no coincidence: every simple polyhedron can be turned into a connected simple planar graph by using the polyhedron's vertices as vertices of the graph and the polyhedron's edges as edges of the graph. The faces of the resulting planar graph then correspond to the faces of the polyhedron. For example, the second planar graph shown above corresponds to a tetrahedron. Not every connected simple planar graph belongs to a simple polyhedron in this fashion: the trees do not, for example. A theorem of Steinitz says that the planar graphs formed from convex polyhedra (equivalently: those formed from simple polyhedra) are precisely the finite graph theory simple planar graphs. === Outerplanar graphs === A graph is called outerplanar if it has an embedding in the plane such that the vertices lie on a fixed circle and the edges lie inside the disk of the circle and don't intersect. Equivalently, there is some face that includes every vertex. Obviously, every outerplanar graph is planar, but the converse is not true: the second example graph shown above (''K''4) is planar but not outerplanar. This is the smallest non-outerplanar graph: a theorem similar to Kuratowski's states that a finite graph is outerplanar if and only if it does not contain a subgraph that is an expansion of ''K''4 (the full graph on 4 vertices) or of ''K''2,3 (five vertices, 2 of which connected to each of the other three for a total of 6 edges). All finite or countable set tree (graph theory) are outerplanar and hence planar. == Other facts and definitions == Every planar graph without loops is 4-partite, or 4-colorable; this is the graph-theoretical formulation of the four color theorem. It can be shown that every simple planar graph admits an embedding in the plane such that all edges are straight line segments which don't intersect. Similarly, every simple outerplanar graph admits an embedding in the plane such that all vertices lie on a fixed circle and all edges are straight line segments that lie inside the disk and don't intersect.
Given an embedding ''G'' of a (not necessarily simple) planar graph in the plane without edge intersections, we construct the dual graph ''G''* as follows: we choose one vertex in each face of ''G'' (including the outer face) and for each edge ''e'' in ''G'' we introduce a new edge in ''G''* connecting the two vertices in ''G''* corresponding to the two faces in ''G'' that meet at ''e''. Furthermore, this edge is drawn so that it crosses ''e'' exactly once and that no other edge of ''G'' or ''G''* is intersected. Then ''G''* is again the embedding of a (not necessarily simple) planar graph; it has as many edges as ''G'', as many vertices as ''G'' has faces and as many faces as ''G'' has vertices. The term "dual" is justified by the fact that ''G''** = ''G''; here the equality is the equivalence of embeddings on the sphere. If ''G'' is the planar graph corresponding to a convex polyhedron, then ''G''* is the planar graph corresponding to the dual polyhedron.
Duals are useful because many properties of the dual graph are related in simple ways to properties of the original graph, enabling results to be proven about graphs by examining their dual graphs.
Graphs
th:กราฟเชิงระนาบ
In Kazimierz Kuratowski, the following version of Kuratowski's theorem was given: :a graph theory with no vertex of order 2 is planar graph if and only if it contains a copy of K5 or K3,3. This statement is incorrect. Take K5, pick one of its edges, say A --- B, and introduce two new vertices X and Y to change the edge to Y | | A --- X --- B The resulting graph is non-planar, has no degree-two vertex, and has no subgraph of form K5 or K3,3. User:AxelBoldt 00:58 13 Jun 2003 (UTC) ---- I removed the paragraph :For a connected planar graph ''G'' we may construct a graph whose vertices are the regions into which ''G'' divides the plane (including a single external region). The edges represent adjacency of regions: there is one for each edge of ''G'', and can be shown as crossing it. The resulting graph ''G''* is naturally also planar: it is called the planar dual graph, or just dual graph, with respect to the given plane embedding of G. We have ''G''** = ''G'', justifying the name ''dual''. The case of a tree shows that ''G''** need not equal ''G'', and so this operation needs to be defined differently to deserve the name "dual". Maybe it should be restricted to graphs arising from simple polyhedra? User:AxelBoldt 19:57, 26 Oct 2003 (UTC) OK, the double dual clearly doesn't work unless crossing an edge takes you into a different region. That looks like the only condition? User:Charles Matthews 06:43, 27 Oct 2003 (UTC) I think so, if we allow our graphs to have multiple edges. User:AxelBoldt 14:24, 27 Oct 2003 (UTC) The dual graph is always taken to be a multigraph and the imbedding in the plane is important. The dual of a tree is a single vertex with a whole lot of loops on it (one loop for each edge of the tree), but the way that the loops are imbedded in the plane (which loops are inside which other loops) encodes the tree structure so it is still true that G** = G. --User:Zero0000 14:59, 27 Oct 2003 (UTC) Aha! Now we're getting somewhere. We only need a clear description of how to get from one embedded connected multigraph to the (or a?) dual embedded multigraph. If ''G'' is the graph consisting of a single edge connecting two vertices, would ''G''* be the one-vertex graph with two separate loops, or with one loop inside the other? Or do we work on the sphere where the two are the same? User:AxelBoldt 09:40, 28 Oct 2003 (UTC) It's a vertex with one loop; you put a vertex in the distinct regions (only 1) and where there's an edge (only 1) you cross it, so you only have a loop. User:Dysprosia 10:03, 28 Oct 2003 (UTC) There is always one edge in G** for each edge of G. The dual of the graph you mention has one vertex with one loop on it. To answer the last part, the imbedding is regarded as being on the sphere for most purposes. That's one of the reasons it's a bit hard to define the concept of a dual precisely without more background theory on the nature of imbeddings. --User:Zero0000 10:10, 28 Oct 2003 (UTC) Oops, above I meant the graph ''G'' with three vertices, connected by two edges. It seems there are the two possibilities for the dual I mentioned above; but if we do work on the sphere they are the same and all is well. User:AxelBoldt 10:25, 28 Oct 2003 (UTC) If you mean something like * \ * / * the dual will be _ / \ | * | \ / o * / \ | * | \_/ (the *s are to show the relative position of the previous vertices) Like Zero mentioned, we have an edge crossing for an edge. We can't have just one loop around that apex vertex. User:Dysprosia 10:28, 28 Oct 2003 (UTC) __________ / _ \ | / \ | \ | * | | \ \ / | -- o * / \ / ---- * would be another possibility for the dual; on a sphere, the two are equivalent, but not in the plane. User:AxelBoldt 11:41, 28 Oct 2003 (UTC) Yepyep :) These graphs are isomorphic, I think, too... User:Dysprosia 11:41, 28 Oct 2003 (UTC) ---- If we allow infinite planar graphs: does Kuratowski remain true for countably infinite graphs? How about the four-color theorem? User:AxelBoldt 13:10, 30 Oct 2003 (UTC) A graph is k-colorable if all its finite subgraphs are k-colorable, so 4CT is true even without the "countable". I think Kuratowski is more complicated. --User:Zero0000 13:41, 30 Oct 2003 (UTC) ---- Kuratowski showed: :that the only non-planar graphs are those that contain a subdivision of K5 or K3,3 obtained by replacing edges with paths. The ''G''** = ''G'' equality holds even for simple connected duals iff the edge-connectivity of ''G'' is strictly greater than 2. --- John Fremlin Sun Jan 18 03:00:37 GMT 2004
See other meanings of words starting from letter:
Words begining with Planar_graph:
Planar_graph
Planar_graph
Planar_graphs
Planar graph
In graph theory, a planar graph is a graph that can be embedded in a plane (mathematics) so that no Edge_(graph_theory)s intersect. For example, the following two graphs are planar: (the second one can be redrawn without intersecting edges by moving one of the diagonal edges to the outside), while the two graphs shown below are ''not'' planar:
It is not possible to redraw these without edge intersections. In fact, these two are the smallest non-planar graphs, a consequence of the characterization below. == Kuratowski's theorem == The Poland mathematician Kazimierz Kuratowski provided a characterization of planar graphs, now known as '''Kuratowski's theorem''': :A finite graph is planar if and only if it does not contain a subgraph that is an ''expansion'' of ''K''5 (the complete graph on 5 vertices) or ''K''3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three). An ''expansion'' of a graph results from inserting vertices into edges, i.e. changing an edge * --- * to * --- * --- *, and repeating this zero or more times. Equivalent formulations of this theorem, also known as "Theorem P" include :A finite graph is planar if and only if it does not contain a subgraph that is homeomorphism (graph theory) to ''K''5 or ''K''3,3. and :A finite graph is planar if and only if it does not have ''K''5 or ''K''3,3 as a minor (graph theory). A far-reaching generalization of Kuratowski's theorem is given by the Robertson-Seymour theorem; in the language of this theorem, ''K''5 and ''K''3,3 are the "forbidden minors" for the class of finite planar graphs. == Other planarity criteria == In practice, it is difficult to use Kuratowski's criterion to quickly decide whether a given graph is planar. However, there exist fast algorithms for this problem: for a graph with ''n'' vertices, it is possible to determine in time Big O notation(''n'') whether the graph is planar or not. For a simple, connected, planar graph with ''n'' vertices and ''e'' edges: : Theorem 1. If ''n'' ≥ 3 then ''e'' ≤ 3''n'' - 6 : Theorem 2. If ''n'' > 3 and there are no cycles of length 3, then ''e'' ≤ 2''n'' - 4 Note that these theorems are if, not if and only if, and therefore can only be used to prove a graph is not planar, not that it is planar. If both theorem 1 and 2 fail, Theorem P must be used. The graph ''K''3,3 has 6 vertices, 9 edges, and no cycles of length 3. Therefore, by Theorem 2, it is not planar. For two planar graphs with ''n'' vertices, it is possible to determine in time O(''n'') whether they are graph theory or not. MacLane's planarity criterion gives an algebraic characterization of finite planar graphs, via their cycle spaces. === Euler's formula === '''Euler's formula''' states that if a finite graph theory planar graph is drawn in the plane without any edge intersections, and ''v'' is the number of vertices, ''e'' is the number of edges and ''f'' is the number of faces (regions bounded by edges, including the outer infinitely large region), then :''v'' − ''e'' + ''f'' = 2, i.e. the Euler characteristic is 2. As an illustration, in the first planar graph given above, we have ''v''=6, ''e''=7 and ''f''=3. If the second graph is redrawn without edge intersections, we get ''v''=4, ''e''=6 and ''f''=4. Euler's formula can be proven as follows: if the graph isn't a tree (graph theory), then remove an edge which completes a cycle. This lowers both ''e'' and ''f'' by one, leaving ''v'' − ''e'' + ''f'' constant. Repeat until you arrive at a tree; trees have ''v'' = ''e'' + 1 and ''f'' = 1, yielding ''v'' - ''e'' + ''f'' = 2. In a finite connected ''simple'' planar graph, any face (except possibly the outer one) is bounded by at least three edges and every edge touches at most two faces; using Euler's formula, one can then show that these graphs are ''sparse'' in the sense that ''e'' ≤ 3''v'' - 6 if ''v'' ≥ 3. A simple graph is called maximal planar if it is planar but adding any edge would destroy that property. All faces (even the outer one) are then bounded by three edges, explaining the alternative term triangular for these graphs. If a triangular graph has ''v'' vertices with ''v'' > 2, then it has precisely 3''v''-6 edges and 2''v''-4 faces. Note that Euler's formula is also valid for simple polyhedron. This is no coincidence: every simple polyhedron can be turned into a connected simple planar graph by using the polyhedron's vertices as vertices of the graph and the polyhedron's edges as edges of the graph. The faces of the resulting planar graph then correspond to the faces of the polyhedron. For example, the second planar graph shown above corresponds to a tetrahedron. Not every connected simple planar graph belongs to a simple polyhedron in this fashion: the trees do not, for example. A theorem of Steinitz says that the planar graphs formed from convex polyhedra (equivalently: those formed from simple polyhedra) are precisely the finite graph theory simple planar graphs. === Outerplanar graphs === A graph is called outerplanar if it has an embedding in the plane such that the vertices lie on a fixed circle and the edges lie inside the disk of the circle and don't intersect. Equivalently, there is some face that includes every vertex. Obviously, every outerplanar graph is planar, but the converse is not true: the second example graph shown above (''K''4) is planar but not outerplanar. This is the smallest non-outerplanar graph: a theorem similar to Kuratowski's states that a finite graph is outerplanar if and only if it does not contain a subgraph that is an expansion of ''K''4 (the full graph on 4 vertices) or of ''K''2,3 (five vertices, 2 of which connected to each of the other three for a total of 6 edges). All finite or countable set tree (graph theory) are outerplanar and hence planar. == Other facts and definitions == Every planar graph without loops is 4-partite, or 4-colorable; this is the graph-theoretical formulation of the four color theorem. It can be shown that every simple planar graph admits an embedding in the plane such that all edges are straight line segments which don't intersect. Similarly, every simple outerplanar graph admits an embedding in the plane such that all vertices lie on a fixed circle and all edges are straight line segments that lie inside the disk and don't intersect.
Planar graph
In Kazimierz Kuratowski, the following version of Kuratowski's theorem was given: :a graph theory with no vertex of order 2 is planar graph if and only if it contains a copy of K5 or K3,3. This statement is incorrect. Take K5, pick one of its edges, say A --- B, and introduce two new vertices X and Y to change the edge to Y | | A --- X --- B The resulting graph is non-planar, has no degree-two vertex, and has no subgraph of form K5 or K3,3. User:AxelBoldt 00:58 13 Jun 2003 (UTC) ---- I removed the paragraph :For a connected planar graph ''G'' we may construct a graph whose vertices are the regions into which ''G'' divides the plane (including a single external region). The edges represent adjacency of regions: there is one for each edge of ''G'', and can be shown as crossing it. The resulting graph ''G''* is naturally also planar: it is called the planar dual graph, or just dual graph, with respect to the given plane embedding of G. We have ''G''** = ''G'', justifying the name ''dual''. The case of a tree shows that ''G''** need not equal ''G'', and so this operation needs to be defined differently to deserve the name "dual". Maybe it should be restricted to graphs arising from simple polyhedra? User:AxelBoldt 19:57, 26 Oct 2003 (UTC) OK, the double dual clearly doesn't work unless crossing an edge takes you into a different region. That looks like the only condition? User:Charles Matthews 06:43, 27 Oct 2003 (UTC) I think so, if we allow our graphs to have multiple edges. User:AxelBoldt 14:24, 27 Oct 2003 (UTC) The dual graph is always taken to be a multigraph and the imbedding in the plane is important. The dual of a tree is a single vertex with a whole lot of loops on it (one loop for each edge of the tree), but the way that the loops are imbedded in the plane (which loops are inside which other loops) encodes the tree structure so it is still true that G** = G. --User:Zero0000 14:59, 27 Oct 2003 (UTC) Aha! Now we're getting somewhere. We only need a clear description of how to get from one embedded connected multigraph to the (or a?) dual embedded multigraph. If ''G'' is the graph consisting of a single edge connecting two vertices, would ''G''* be the one-vertex graph with two separate loops, or with one loop inside the other? Or do we work on the sphere where the two are the same? User:AxelBoldt 09:40, 28 Oct 2003 (UTC) It's a vertex with one loop; you put a vertex in the distinct regions (only 1) and where there's an edge (only 1) you cross it, so you only have a loop. User:Dysprosia 10:03, 28 Oct 2003 (UTC) There is always one edge in G** for each edge of G. The dual of the graph you mention has one vertex with one loop on it. To answer the last part, the imbedding is regarded as being on the sphere for most purposes. That's one of the reasons it's a bit hard to define the concept of a dual precisely without more background theory on the nature of imbeddings. --User:Zero0000 10:10, 28 Oct 2003 (UTC) Oops, above I meant the graph ''G'' with three vertices, connected by two edges. It seems there are the two possibilities for the dual I mentioned above; but if we do work on the sphere they are the same and all is well. User:AxelBoldt 10:25, 28 Oct 2003 (UTC) If you mean something like * \ * / * the dual will be _ / \ | * | \ / o * / \ | * | \_/ (the *s are to show the relative position of the previous vertices) Like Zero mentioned, we have an edge crossing for an edge. We can't have just one loop around that apex vertex. User:Dysprosia 10:28, 28 Oct 2003 (UTC) __________ / _ \ | / \ | \ | * | | \ \ / | -- o * / \ / ---- * would be another possibility for the dual; on a sphere, the two are equivalent, but not in the plane. User:AxelBoldt 11:41, 28 Oct 2003 (UTC) Yepyep :) These graphs are isomorphic, I think, too... User:Dysprosia 11:41, 28 Oct 2003 (UTC) ---- If we allow infinite planar graphs: does Kuratowski remain true for countably infinite graphs? How about the four-color theorem? User:AxelBoldt 13:10, 30 Oct 2003 (UTC) A graph is k-colorable if all its finite subgraphs are k-colorable, so 4CT is true even without the "countable". I think Kuratowski is more complicated. --User:Zero0000 13:41, 30 Oct 2003 (UTC) ---- Kuratowski showed: :that the only non-planar graphs are those that contain a subdivision of K5 or K3,3 obtained by replacing edges with paths. The ''G''** = ''G'' equality holds even for simple connected duals iff the edge-connectivity of ''G'' is strictly greater than 2. --- John Fremlin
See other meanings of words starting from letter:
P
PA | PB | PC | PD | PE | PF | PG | PH | PI | PJ | PK | PL | PM | PN | PO | PR | PS | PT | PU | PW | PX | PY | PZ |Words begining with Planar_graph:
Planar_graph
Planar_graph
Planar_graphs
These materials are based on Wikipedia and licensed under the GNU FDL
YouTube.com videos better site than Turbo Tax 2007
