Name
Title | ||
|---|---|---|
Dissections and trees, with applications to optimal mesh encoding and to random sampling |
Abstract | ||
|---|---|---|
We present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees. This correspondence has interesting consequences for enumeration, mesh compression and random graph sampling.It yields a succinct representation for the set P(n) of n-edge 3-connected planar graphs matching the entropy bound 1/n log |P(n)| = 2+o(1) bits per edge. This solves a theoretical problem in mesh compression, as these graphs abstract the combinatorial part of meshes with spherical topology.Once the entropy bound is matched, the guaranteed compression rate can only be improved on subclasses: we achieve the optimal parametric rate 1/n log |P(n, i, j)| bits per edge for graphs of P(n) with i vertices and j faces. This effectively reduces the entropy as soon as |i -j| ≫ n1/2, and achieves the optimal rate for triangulations.It also yields an efficient uniform random sampler for labeled 3-connected planar graphs. Using it, the amortized complexity of sampling labeled planar graphs is reduced from the best previously known O(n6.5) to O(n3). |
Year | DOI | Venue |
|---|---|---|
2005 | 10.5555/1070432.1070529 | SODA |
Keywords | Field | DocType |
n log,3-connected planar graph,optimal rate,random graph sampling,planar graph,efficient uniform random sampler,mesh compression,guaranteed compression rate,i vertex,mesh encoding,optimal parametric rate,random sampling,random graph,binary tree,greedy algorithm | Random regular graph,Discrete mathematics,Data compression ratio,Combinatorics,Bijection,Random graph,Vertex (geometry),Chordal graph,Amortized analysis,Mathematics,Planar graph | Conference |
ISBN | Citations | PageRank |
0-89871-585-7 | 19 | 1.01 |
References | Authors | |
16 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Éric Fusy | 1 | 198 | 21.95 |
| Dominique Poulalhon | 2 | 127 | 9.73 |
| Gilles Schaeffer | 3 | 423 | 44.82 |