A Master Bijection for Planar Maps, and Its Applications

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=9cKUFIz896Y


Duration: 50:00
73 views
0

Planar maps are embeddings of connected planar graphs in the plane considered up to continuous deformation. We will present a ``master bijection'' for planar maps and show that it can be specialized in various ways in order to count several families of maps. More precisely, for each integer d we obtain a bijection between the family of maps of girth d and a family of decorated plane trees. This gives new counting results for maps of girth d counted according to the degree distribution of their faces. Our approach unifies and extends many known bijections. A key ingredient in the proofs are classes of orientations generalizing Schnyder woods. This is a joint work with Eric Fusy.



Other Videos By Microsoft Research


2016-08-16Fine-Grained Power Modeling for Smartphones Using System Call Tracing
2016-08-16Reputational Bargaining Under Knowledge of Rationality
2016-08-16We Will be Right With You: Managing Customers Expectations with Vague Promises and Cheap Talk
2016-08-16Information That Matters: Investigating Relevance of Entities in Social Media Networks
2016-08-16Efficient Bayesian Algorithmic Mechanism Design
2016-08-16Extreme Learning Machine: Learning Without Iterative Tuning
2016-08-16Extracting Knowledge from Networks: Rumors, Superstars, and Communities
2016-08-16Electrical Flows and Laplacian Systems: A New Tool for Graph Algorithms
2016-08-16Limit Theorems in Pseudorandomness and Learning Theory
2016-08-16Empirical Software Engineering, Version 2.0
2016-08-16A Master Bijection for Planar Maps, and Its Applications
2016-08-16Password-based Authenticated Key Exchange at the Cost of Diffie-Hellman
2016-08-16Generalized Identity-Based Encryption
2016-08-16Cryptography with Weak, Noisy, Leaky and Tempered Keys
2016-08-16Electrical Flows and Laplacian Systems: A New Tool for Graph Algorithms
2016-08-16Broadcast Based Peer Review in Open Source Software Development Projects
2016-08-16Optimization under Uncertainty: Understanding the Correlation Gap
2016-08-16Computational Social Choice: Algorithmic, Strategic, and Combinatorial Aspects
2016-08-16Harvesting and Querying the World's Knowledge
2016-08-16The FT-Mollification Method
2016-08-16Getting More: How to Negotiate to Achieve Your Goals in the Real World


Tags:
microsoft research