English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We present a bijection between some quadrangular dissections of an hexagonand unrooted binary trees, with interesting consequences for enumeration, meshcompression and graph sampling. Our bijection yields an efficient uniformrandom sampler for 3-connected planar graphs, which turns out to be determinantfor the quadratic complexity of the current best known uniform random samplerfor labelled planar graphs [{\bf Fusy, Analysis of Algorithms 2005}]. It alsoprovides an encoding for the set $\mathcal{P}(n)$ of $n$-edge 3-connectedplanar graphs that matches the entropy bound$\frac1n\log_2|\mathcal{P}(n)|=2+o(1)$ bits per edge (bpe). This solves atheoretical problem recently raised in mesh compression, as these graphsabstract the combinatorial part of meshes with spherical topology. We alsoachieve the {optimal parametric rate} $\frac1n\log_2|\mathcal{P}(n,i,j)|$ bpefor graphs of $\mathcal{P}(n)$ with $i$ vertices and $j$ faces, matching inparticular the optimal rate for triangulations. Our encoding relies on a lineartime algorithm to compute an orientation associated to the minimal Schnyderwood of a 3-connected planar map. This algorithm is of independent interest,and it is for instance a key ingredient in a recent straight line drawingalgorithm for 3-connected planar graphs [\bf Bonichon et al., Graph Drawing2005].

Dissections, orientations, and trees, with applications to optimal mesh encoding and to random sampling