ICS Theory Group

Spring 2017: Theory Seminar
Bren Hall, Room 1423, 1:00pm


May 19, 2017:

Square Contact Representations of Simply Nested k-Outerplanar Graphs

Tim Johnson

Abstract: Geometric graph drawing has been studied for decades, but while strong results are known for drawings that use rectangles or circles, little progress has been made on drawing graphs with squares. We provide the first new step in many years by proving that the simply nested 2-outerplanar graphs have square contact representations. We also provide an example of a simply nested 3-outerplanar graph that has no such representation.