vertices, it is possible to determine in time (linear time) whether the graph may be planar or not (see planarity testing).

For a simple, connected, planar graph with vertices and edges and faces, the following simple conditions hold for :

* Theorem 1. ;
* Theorem 2. If there are no cycles of length 3, then .
* Theorem 3. .

In this sense, planar graphs are sparse graphs, in that they have only edges, asymptotically smaller