To represent a graph in a geometric way is a very natural and old problem. For example, it was proved by Steinitz early in this century that every 3-connected planar graph can be represented as the graph of vertices and edges of a (3-dimensional) polytope.

Representability of a graph in various geometric fashions turns out to be closely related to a number of basic properties and invariants of the graph: chromatic number, clique number, connectivity, maximum cuts, etc. Moreover, computing these representations often helps in the design of algorithms for purely graph-theoretic problems.

Geometric Representations and Graph Properties

Orthogonal Representations and Semidefinite Optimization

Colin de Verdiere’s Invariant