Geometric Realizations of n-Vertex Graphs


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
 


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of VermontBurlingtonVT 05401-1455 USA (with thanks to Janos Pach)

Send comments to dan.archdeacon@uvm.edu

December 2003