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.