FACTOID # 1: Idaho produces more milk than Iowa, Indiana and Illinois combined.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Planar graph
Example graphs
Planar Nonplanar
K5
K5
The complete graph K4 is planar
The complete graph K4 is planar
K3,3
K3,3

In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. A nonplanar graph cannot be drawn in the plane without edge intersections. Image File history File links 6n-graf. ... Image File history File links 6n-graf. ... Image File history File links Complete_graph_K5. ... Image File history File links Complete_graph_K5. ... Image File history File links CGK4PLN.svg‎ File historyClick on a date/time to view the file as it appeared at that time. ... Image File history File links CGK4PLN.svg‎ File historyClick on a date/time to view the file as it appeared at that time. ... In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ... Image File history File links Complete_bipartite_graph_K3,3. ... Image File history File links Complete_bipartite_graph_K3,3. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... This article just presents the basic definitions. ... In mathematics, an embedding (or imbedding) is one instance of some mathematical object contained within another instance, such as a group that is a subgroup. ... Two intersecting planes in three-dimensional space In mathematics, a plane is a two-dimensional manifold or surface that is perfectly flat. ...


A planar graph already drawn in the plane without edge intersections is called a plane graph. A plane graph can be defined as a planar graph with a mapping from every node to a position in 2D space, and from every edge to a plane curve, such that each curve has two extreme points, which coincide with the positions of its end nodes, and all curves are disjoint except on their extreme points. In mathematics, the concept of a curve tries to capture our intuitive idea of a geometrical one-dimensional and continuous object. ...


The equivalence class of topologically equivalent drawings on the sphere is called a planar map. Although a plane graph has an external or unbounded face, none of the faces of a planar map has a particular status.

Contents

Kuratowski's and Wagner's theorems

The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs, now known as Kuratowski's theorem: Kazimierz Kuratowski (born February 2, 1896, Warsaw, died June 18, 1980, Warsaw) was a Polish mathematician. ...

A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or K3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three).

A subdivision of a graph results from inserting vertices into edges (for example, changing an edge •——• to •—•—•) and repeating this zero or more times. Equivalent formulations of this theorem, also known as "Theorem P" include An undirected graph with 6 vertices (nodes) and 7 edges. ... It has been suggested that this article or section be merged into Logical biconditional. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ... This article just presents the basic definitions. ... In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ...

A finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to K5 or K3,3.

In the Soviet Union, Kuratowski's theorem was known as the Pontryagin-Kuratowski theorem, as its proof was allegedly first given in Pontryagin's unpublished notes. By a long-standing academic tradition, such references are not taken into account in determining priority, so the Russian name of the theorem is not acknowledged internationally. A homeomorphism in graph theory exists between two graphs G and G′ if there exists a graph that can be found from subdivision of edges in that graph. ... Lev Semenovich Pontryagin (Russian: Лев Семёнович Понтрягин) (3 September 1908- 3 May 1988) was a Soviet/Russian mathematician. ...

Here is an example of a graph which doesn't have K5 or K3,3 as its subgraph. But it has a subgraph that is homeomorphic to K3,3
Here is an example of a graph which doesn't have K5 or K3,3 as its subgraph. But it has a subgraph that is homeomorphic to K3,3

Instead of considering subdivisions, Wagner's theorem deals with minors: Image File history File links Nonplanar_no_subgraph_K_3_3. ... In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that results from a subgraph of G by zero or more edge contractions. ...

A finite graph is planar if and only if it does not have K5 or K3,3 as a minor.

Wagner asked more generally whether any minor-closed class of graphs is determined by a finite set of "forbidden minors". This is now the Robertson-Seymour theorem, proved in a long series of papers. In the language of this theorem, K5 and K3,3 are the forbidden children for the class of finite planar graphs. In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that results from a subgraph of G by zero or more edge contractions. ... In graph theory, the Robertson-Seymour theorem states that every downwardly closed set of (isomorphism classes of) finite graphs is precisely the set of all (isomorphism classes of) graphs that lack a certain set of finitely many forbidden minors. ... In graph theory, the Robertson-Seymour theorem states that every downwardly closed set of (isomorphism classes of) finite graphs is precisely the set of all (isomorphism classes of) graphs that lack a certain set of finitely many forbidden minors. ...


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 O(n) (linear time) whether the graph is planar or not. In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... Big O notation is often used to describe how the size of the input data affects an algorithms running time. ...


For a simple, connected, planar graph with v vertices and e edges, the following simple planarity criteria hold:

Theorem 1. If v ≥ 3 then e ≤ 3v - 6
Theorem 2. If v > 3 and there are no cycles of length 3, then e ≤ 2v - 4

In this sense, planar graphs are sparse graphs, in that they have only O(v) edges, asymptotically smaller than the maximum O(v2). The graph K3,3, for example, has 6 vertices, 9 edges, and no cycles of length 3. Therefore, by Theorem 2, it can not be planar. Note that these theorems provide necessary conditions for planarity that are not sufficient conditions, 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, other methods may be used. In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ...


For two planar graphs with v vertices, it is possible to determine in time O(v) whether they are isomorphic or not. A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ...

  • Whitney's planarity criterion gives a characterization based on the existence of an algebraic dual;
  • MacLane's planarity criterion gives an algebraic characterization of finite planar graphs, via their cycle spaces;
  • Fraysseix-Rosenstiehl's planarity criterion gives a characterization based on the existence of a bipartition of the cotree edges of a depth-first search tree. It is central to the left-right planarity testing algorithm;
  • Schnyder's theorem gives a characterization of planarity in terms of partial order dimension;
  • Colin de Verdière's planarity criterion gives a characterization based on the maximum multiplicity of the second eigenvalue of certain Schrödinger operators defined by the graph.

G′is the dual graph of G Let G be a connected planar graph with a particular embedding in the plane, in other words, drawn without edge intersections. ... In graph theory, Mac Lanes planarity criterion is a characterisation of planar graphs in terms of their cycle spaces. ... // The binary cycle space In graph theory, certain vector spaces over the two-element field Z2 are associated with an undirected graph; this allows one to use the tools of linear algebra to study graphs. ... In mathematics, Fraysseix-Rosenstiehls planarity criterion in graph theory is based on the properties of the tree defined by a depth-first search. ... Schnyders theorem is a planarity characterization for graphs in terms of the order dimension of their incidence posets. ... In mathematics, if P and Q be posets on the same set X, Q is an extension of P if in P implies in Q, for all . ... Colin de Verdières invariant is a graph parameter for any graph G which has been introduced by Colin de Verdière in 1990, motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators. ...

Euler's formula

Euler's formula states that if a finite, connected, 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 A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ...

ve + 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, then remove an edge which completes a cycle. This lowers both e and f by one, leaving ve + f constant. Repeat until you arrive at a tree; trees have v = e + 1 and f = 1, yielding v - e + f = 2. It has been suggested that Vertex/Face/Edge relation in a convex polyhedron be merged into this article or section. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... Cycle in graph theory and computer science has several meanings: A closed walk, with repeated vertices allowed. ...


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 ≤ 3v - 6 if v ≥ 3. In mathematics and computer science, graph theory studies the properties of graphs. ... This article just presents the basic definitions. ...


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 3v-6 edges and 2v-4 faces.


Note that Euler's formula is also valid for simple polyhedra. 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 Ernst Steinitz says that the planar graphs formed from convex polyhedra (equivalently: those formed from simple polyhedra) are precisely the finite 3-connected simple planar graphs. A polyhedron (plural polyhedra or polyhedrons) is a geometric object with flat faces and straight edges. ... A tetrahedron (plural: tetrahedra) is a polyhedron composed of four triangular faces, three of which meet at each vertex. ... Ernst Steinitz (June 13, 1871 – September 29, 1928) was an German mathematician. ... Look up Convex set in Wiktionary, the free dictionary. ... In mathematics and computer science the connectivity of graphs is one of the basic concepts of graph theory. ...


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. Every outerplanar graph is planar, but the converse is not true: the second example graph shown above (K4) 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 K4 (the full graph on 4 vertices) or of K2,3 (five vertices, 2 of which connected to each of the other three for a total of 6 edges). Circle illustration This article is about the shape and mathematical concept of circle. ... In geometry, a disk is the region in a plane contained inside of a circle. ...


Properties of outerplanar graphs

All finite or countably infinite trees are outerplanar and hence planar. In mathematics, a countable set is a set with the same cardinality (i. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...


An outerplanar graph has a vertex of degree at most 2 or a looped vertex of degree 4. [citation needed] [otherwise there must be at least 4 vertices of degree at least 3 or looped vertices of degree at least 5; such a graph can be retracted to a K4.]


All loopless outerplanar graphs are 3-colorable. [citation needed]


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. Image:3-colouringEx. ... Example of a four-colored map The four color theorem (also known as the four color map theorem) states that given any plane separated into regions, such as a political map of the states of a country, the regions may be colored using no more than four colors in such...


Fáry's theorem states 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. Fárys theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. ... A line, or straight line, is, roughly speaking, an (infinitely) thin, (infinitely) long, straight geometrical object, i. ...

A planar graph and its dual
A planar graph and its dual

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. Image File history File links Dual_graphs. ... Image File history File links Dual_graphs. ... G′is the dual graph of G Dual graph is a term used in the mathematical study of graphs. ... G′is the dual graph of G Dual graph is a term used in the mathematical study of graphs. ... A sphere is a perfectly symmetrical geometrical object. ...


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.


External links

References

  • Kazimierz Kuratowski (1930), 'Sur le problème des courbes gauches en topologie'. Fund. Math., 15, pp. 271-283.
  • K. Wagner (1937), 'Über eine Eigenschaft der ebenen Komplexe', Math. Ann. 114, pp. 570–590.
  • John M. Boyer and Wendy J. Myrvold (2005), 'On the cutting edge: Simplified O(n) planarity by edge addition'. Journal of Graph Algorithms and Applications, vol. 8 no. 3, pp. 241-273.
  • Brendan McKay & Gunnar Brinkmann, A useful planar graph generator
  • H. de Fraysseix, P. Ossona de Mendez & P. Rosenstiehl (2006). 'Trémaux trees and planarity'. International Journal of Foundations of Computer Science, vol. 17 no. 5, pp. 1017-1029. Special Issue on Graph Drawing. doi:10.1142/S0129054106004248
  • D.A. Bader and S. Sreshta, A New Parallel Algorithm for Planarity Testing, UNM-ECE Technical Report 03-002, October 1, 2003.

  Results from FactBites:
 
Springer Online Reference Works (0 words)
A planar map each side of which is bounded by three edges is said to be a planar triangulation.
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.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m