Overlap and Intersection Representations of Planar Graphs by Squares

Steve Chaplick

Abstract

A graph G=(V,E) is an intersection graph of squares when every vertex of G can be represented by an axis-parallel square in the plane so that two vertices are adjacent if and only if their corresponding squares intersect. Similarly, G is an overlap graph of squares when the corresponding squares overlap (i.e., intersection graphs of ``frames'' of squares). We prove that every 4-connected planar graph is an intersection graph of squares and that every planar graph is an overlap graph of squares.

This is joint work with Torsten Ueckerdt.