CS 269S, Fall 2010: Theory Seminar
CS Building, Room 243
19 Nov 2010:

Succinct Convex Greedy Drawing of 3-Connected Plane Graphs

Lowell Trott

The authors show that the classical Schnyder drawing in R2 of 3-connected plane graphs is weakly greedy with respect to a metric function H(*,*). The drawing is planar, convex, and succinct, using two integer coordinates between 0 and f, where f is the number of internal faces of the graph.

(Based on a paper by He and Zhang to appear at SODA 2011.)