There are many different approaches to drawing graphs; edges as straight lines or splines, or orthogonal chains, vertices as boxes or circles or points, faces as rectangles or orthogonal polygons. An interesting graph drawing result on planar graphs is Fary's theorem:

Any planar graph can be drawn with straight lines for edges and no crossings.

Any planar graph can be drawn with straight lines for edges and no crossings.

What makes the above result quite interesting is the following. Let a

*pseudoline arrangement*be a collection of curves (each separating the plane into two parts) in which each pair intersects exactly once. Such a collection defines an arrangement of the plane (with faces, vertices and edges). Such an arrangement is

*stretchable*if it is isomorphic to a straight line arrangement.

*Not all pseudoline arrangements are stretchable. In fact, determining whether a given pseudoline arrangement is stretchable is NP-hard*(due to Peter Shor).