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.
[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
Send comments to firstname.lastname@example.org