Integer representations of convex polygon intersection graphs
Tobias Müller, Erik Jan van Leeuwen, Jan Van Leeuwen · 2011
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 Ω(n2) x Ω(n2) 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.