SFU Discrete Math Seminar: Stephen Kobourov

  • Date: 02/15/2023
  • Time: 11:30
Lecturer(s):
Stephen Kobourov, University of Arizona
Location: 

Simon Fraser University

Topic: 

Contact Representation of Planar Graphs in 2D and 3D

Description: 

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.

Other Information: 

Location: SFU - SCK 9509

Time: 11.30am Pacific