A *geometric graph* is a graph drawn in the plane such that *a)*
no three vertices are colinear and *b)* edges are straight line segments.
Edges are allowed to cross, but only transversally at interior points.

**Problem:** *Find the minimum cardinality *f(n) *of a point
set* P *in the plane such every planar graph* H *of order*
n *can be realized by a crossing-free geometric drawing using only the
points in* P.

The function *f(n)* is known to be *O(n^2) *([FPP], see also
[S]) *.* In particular, *P* can be chosen to as a subset of the
*n* x *2n* integer grid.

**References:**

[FPP] H. deFraysseix, J. Pach, and R. Pollack, How to draw a planar
graph on a grid, *Combinatorica* **10** (1990) 41-51

[S] W. Schnyder, Embedding planar graphs on the grid, *First Annual
ACM-SIAM Symposium on Discrete Algorithms*, SIAM, Philadelphia, Pennslyvania
(1990) 138-147

Send comments to *dan.archdeacon@uvm.edu*

December 2003