Schnyder woods for higher genus surfaces: from graph encoding to graph drawing 🗓 🗺

Speaker

Luca Castelli Aleardi
Laboratoire d’Informatique (LIX), Ecole Polytechnique

Where and When

Martedì 28 aprile 2015 Ore 15:00-16:00
Sala Riunioni, 1° piano, Dipartimento di Ingegneria
Via della Vasca Navale, 79, Roma

Abstract

Planar graphs play a fundamental role in computer science, discrete
mathematics and related fields.
Among their properties, a deep and nice characterization is the one
provided in terms of edge orientations, now referred to as Schnyder woods.
W. Schnyder introduced a new combinatorial structure to define a new
planarity criterion: he proved that a graph is planar if and only if its
incidence poset (incident relations between vertices and edges) has
dimension at most 3.
Schnyder woods have led to a surprisingly large number of applications (in
graph drawing, bijective enumeration, random sampling, graph encoding,
contact representations, greedy routing). Unfortunately, these structures
are originally only defined for planar graphs.
This talk focuses on the recent generalizations of Schnyder woods to the
case of toroidal and higher genus surfaces, and its algorithmic
applications in the domains of graph encoding and graph drawing.