On 22.10.2014 at 10:40 in S1, there is the following noon lecture:
Overlap and Intersection Representations of Planar Graphs by Squares
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.
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019