Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer 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.

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

Webmaster: kamweb.mff.cuni.cz         Archive page