ICS Theory Group

Winter 2017: Theory Seminar
Bren Hall, Room 1300, 1:00pm

January 20, 2017:

Square Dissections and Square Contact Representations

Will Devanny

A square contact representation is a representation of a graph where interior disjoint squares are used to represent vertices and edges of the graph correspond to side-side contacts between pairs of squares. One way to define a square dissection is as a square contact representation where the union of the squares forms a rectangle. It is an open question whether or not bipartite planar graphs admit square contact representations. We will present a selection of results on square dissections and square contact representations from “Rectangle and Square Representations of Planar Graphs”, a survey by Felsner, along with a couple of modest steps by Alam, Da Lozzo, D., and Johnson towards classifying which graphs admit square contact representations.