The convex dimension of a graph $G=(V,E)$ is the smallest
dimension d for which G admits an embedding $f:V \rightarrow R^d$
of its vertices into $d$-space, such that the barycenters of
the images of its edges are in convex position. We say that $d$ is
the strong convex dimension of $G$ if the above condition is
augmented with the requirement that the image of the vertices of
$G$ are in convex position. The convex and strong convex dimensions
of graphs arise naturally in connection with a special class of convex
combinatorial optimization problems. In this talk we will study the convex and strong convex dimensions and the extremal number of edges of graphs with given convex dimension.

Joint work with Shmuel Onn (Technion) and Uriel G. Rothblum (Technion).