Contact Representation of Planar Graphs in 2D and 3D

Stephen Kobourov, University of Arizona, Tucson

Date and time: 2pm, Friday, September 21, 2018

Place: CUNY Graduate Center, Rm 4419

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. We show how to use Schnyder realizers and canonical orders for planar graphs to obtain different types of contact representations. Specifically, we describe an algorithm that constructs proportional contact representation for arbitrary planar graphs using 10-sided rectilinear polygons. We also describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity, as 8-sided polygons are sometimes necessary. In 3D vertices are represented by polytopes and edges by contacts between the corresponding polytopes contacts. We show that planar 3-trees have contact representations with cubes and proportional contact representations with boxes.

Bio: Stephen Kobourov is a Professor of Computer Science at the University of Arizona. He completed BS degrees in Mathematics and Computer Science at Dartmouth College in 1995, and a PhD in Computer Science at Johns Hopkins University in 2000. He has worked as a Research Scientist at AT&T Research Labs, a Hulmboldt Fellow at the University of Tübingen in Germany, and a Distinguished Fulbright Chair at Charles University in Prague.