integer representations of convex polygon intersection graphs
We give the first lower bounds on the grid size needed to represent the intersection graphs of~convex polygons. Here each corner of a polygon in the representation must lie on a corner of the grid. We provide a series of geometric constructions showing that for intersection graphs of: translated copies of any fixed parallelogram, grids of size ?(n 2 ) x ?(n 2 ) are needed; translated copies of any other fixed convex polygon, grids of size 2 ?(n) x 2 ?(n) are needed; homothetic copies of any fixed convex polygon, grids of size 2 ?(n) x 2 ?(n) are needed. We complement these results by giving a matching upper bound in each case. Hence we settle the complexity of the integer representation problem for these graphs. The upper bounds substantially improve earlier bounds and extend to higher dimensions.
integer representation convex polygons upper and lower bounds geometric intersection graphs