 Main
Classes of graphs embeddable in orderdependent surfaces
Abstract
Given a function \(g=g(n)\) we let \(\mathcal{E}^g\) be the class of all graphs \(G\) such that if \(G\) has order \(n\) (that is, has \(n\) vertices) then it is embeddable in some surface of Euler genus at most \(g(n)\), and let \(\widetilde{\mathcal E}^g\) be the corresponding class of unlabelled graphs. We give estimates of the sizes of these classes. For example we show that if \(g(n)=o(n/\log^3n)\) then the class \(\mathcal{E}^{g}\) has growth constant \(\gamma_{\mathcal{P}}\), the (labelled) planar graph growth constant; and when \(g(n) = O(n)\) we estimate the number of nvertex graphs in \(\mathcal{E}^{g}\) and \(\widetilde{\mathcal E}^g\) up to a factor exponential in \(n\). From these estimates we see that, if \(\mathcal{E}^g\) has growth constant \(\gamma_{\mathcal{P}}\) then we must have \(g(n)=o(n/\log n)\), and the generating functions for \(\mathcal{E}^g\) and \(\widetilde{\mathcal E}^g\) have strictly positive radius of convergence if and only if \(g(n)=O(n/\log n)\). Such results also hold when we consider orientable and nonorientable surfaces separately. We also investigate related classes of graphs where we insist that, as well as the graph itself, each subgraph is appropriately embeddable (according to its number of vertices); and classes of graphs where we insist that each minor is appropriately embeddable. In a companion paper, these results are used to investigate random \(n\)vertex graphs sampled uniformly from \(\mathcal{E}^g\) or from similar classes.
Mathematics Subject Classifications: 05C10, 05C30
Keywords: Embeddable graphs, orderdependent surfaces, approximate counting, labelled graphs
Main Content
Enter the password to open this PDF file:













