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 , 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 .
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.