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