Grid Representations and the Chromatic Number

Martin Balko

A grid drawing of a graph maps vertices to grid points and edges to line segments that avoid grid points representing other vertices. We show that there is a number of grid points…