planar graph


Also found in: Wikipedia.

planar graph

[′plā·nər ‚graf]
(mathematics)
A graph that can be drawn in a plane without any lines crossing.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
References in periodicals archive ?
Let G = (V(G), E(G), F(G)) be aconnected planar graph with V(G) being its number of vertices, E(G) being its number of edges, and F(G) being its number of faces; it has no loops and no parallel edges.
A plane graph is a particular drawing of a planar graph on the Euclidean plane.
The well-known observation for a planar graph G ismad(G) < 2g(G)/(g(G)-2).
Hadlock, "Finding a maximum cut of a planar graph in polynomial time," SIAM Journal on Computing, vol.
The current best algorithm for 4-coloring an m-vertex planar graph runs in O([m.sup.2]) time [34], and a repeated call to this algorithm to exponentially decaying bar-visibility graphs takes O([n.sup.2]) time.
In particular, one well-known result of Schnyder states that every planar graph has arboricity at most 3, see [5].
Corresponding to every connected link diagram we can find a connected signed planar graph and vice versa.
In a maximal planar graph G = ((V (G), E(G)) with [absolute value of V (G)]=n and [absolute value of E (G)]=m, we have m = 3n - 6.
From the view of graph theory, polymino is a finite 2-connected planar graph and each interior face is surrounded by a square with length 4.
Also, observe that a planar graph divides the plane into several faces; there is only one unbounded face; and any bounded face corresponds to a cycle.
There's an interactive planar graph as well that can be rotated with your mouse.