# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

On 22.10.2014 at 10:40 in S1, there is the following noon lecture:

# 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.

Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019