On the number of planar orientations with prescribed degrees

zbMATH Open1182.05058arXivmath/0701771MaRDI QIDQ1010800FDOQ1010800

Stefan Felsner, Florian Zickfeld

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We deal with the asymptotic enumeration of combinatorial structures on planar maps. Prominent instances of such problems are the enumeration of spanning trees, bipartite perfect matchings, and ice models. The notion of orientations with out-degrees prescribed by a function $aa:VoNN$ unifies many different combinatorial structures, including the afore mentioned. We call these orientations $aa$-orientations. The main focus of this paper are bounds for the maximum number of $aa$-orientations that a planar map with $n$ vertices can have, for different instances of $aa$. We give examples of triangulations with $2.37^n$ Schnyder woods, 3-connected planar maps with $3.209^n$ Schnyder woods and inner triangulations with $2.91^n$ bipolar orientations. These lower bounds are accompanied by upper bounds of $3.56^n$, $8^n$ and $3.97^n$ respectively. We also show that for any planar map $M$ and any $alpha$ the number of $alpha$-orientations is bounded from above by $3.73^n$ and describe a family of maps which have at least $2.598^n$ $alpha$-orientations.

Full work available at URL: https://arxiv.org/abs/math/0701771

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

asymptotic enumerationplanar mapsnumber of \(\alpha\)-orientations

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30)

Cited In (14)

• Bijections for Baxter families and related objects
• New upper bounds for the number of embeddings of minimally rigid graphs
• Distance between \(\alpha\)-orientations of plane graphs by facial cycle reversals
• Mixing Times of Markov Chains of 2-Orientations
• Straight line triangle representations
• Planar orientations with low out-degree and compaction of adjacency matrices
• Counting planar Eulerian orientations
• Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings
• Symmetries of unlabelled planar triangulations
• On the order dimension of outerplanar maps
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
• On the area requirements of planar greedy drawings of triconnected planar graphs
• Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators
• Sampling and counting 3-orientations of planar triangulations

Uses Software

• OEIS

This page was built for publication: On the number of planar orientations with prescribed degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010800)