Episódio 2 | flashx VF BDRIP | construct 3

On random planar graphs, the number of planar graphs and their triangulations

On random planar graphs, the number of planar graphs and their triangulations

Journal of Combinatorial Theory, Series B 88 (2003) 119–134 http://www.elsevier.com/locate/jctb On random planar graphs, the number of planar graphs...

219KB Sizes 2 Downloads 19 Views

Journal of Combinatorial Theory, Series B 88 (2003) 119–134

http://www.elsevier.com/locate/jctb

On random planar graphs, the number of planar graphs and their triangulations Deryk Osthus, Hans Ju¨rgen Pro¨mel, and Anusch Taraz Institut fu¨r Informatik, Humboldt-Universita¨t zu Berlin, Unter den Linden 6, 10099 Berlin, Germany Received 24 April 2001

Abstract Let Pn be the set of labelled planar graphs with n vertices. Denise, Vasconcellos and Welsh proved that jPn jpn! ð75:8ÞnþoðnÞ and Bender, Gao and Wormald proved that jPn jXn! ð26:1ÞnþoðnÞ : Gerke and McDiarmid proved that almost all graphs in Pn have at least 13=7n edges. In this paper, we show that jPn jpn! ð37:3ÞnþoðnÞ and that almost all graphs in Pn have at most 2:56n edges. The proof relies on a result of Tutte on the number of plane triangulations, the above result of Bender, Gao and Wormald and the following result, which we also prove in this paper: every labelled planar graph G with n vertices and m edges is contained in at least e3ð3nmÞ=2 labelled triangulations on n vertices, where e is an absolute constant. In other words, the number of triangulations of a planar graph is exponential in the number of edges which are needed to triangulate it. We also show that this bound on the number of triangulations is essentially best possible. r 2002 Elsevier Science (USA). All rights reserved.

1. Introduction Compared to the wealth of knowledge one has about random graphs in general, rather little is known about the likely properties of a random planar graph on n vertices—not even the expected number of edges. Here we consider the uniform model: let Pn be the set of labelled planar graphs with vertex set f1; y; ng: A random planar graph Pn is chosen uniformly from Pn : This should not be confused with a random planar map, since a planar map is defined as a connected graph which is embedded in the plane, whereas a planar graph may have several embeddings. E-mail addresses: [email protected] (D. Osthus), [email protected] . (H.J. Promel), [email protected] (A. Taraz). 0095-8956/03/$ - see front matter r 2002 Elsevier Science (USA). All rights reserved. doi:10.1016/S0095-8956(02)00040-0

120

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

Moreover, we consider only simple graphs whereas maps may usually have multiple edges. Random planar graphs were first investigated by Denise et al. [2]. They showed that n! 6nþoðnÞ pjPn jpn! ð75:8ÞnþoðnÞ ; that the limiting probability that Pn is connected is greater than zero and that the expected number of edges of Pn is at least 3n=2: They also introduced a Markov chain whose stationary distribution is the uniform measure on Pn : This Markov chain was investigated in much more detail by Gerke and McDiarmid [4], who showed that almost surely Pn has at least 13n=7 edges. Complementing the result of [2] on the connectivity of Pn ; McDiarmid et al. [6] proved (amongst other results) that the limiting probability that Pn is connected is less than one. Using generating function techniques, Bender et al. [1] proved that the number of 2-connected graphs in Pn is, in fact, asymptotically Cn!an n7=2 ; where C is some positive constant and aB26:1876; which gives the best-known lower bound on jPn j: Concerning upper bounds on jPn j; in the final section we will prove upper bounds for the number of graphs in Pn with a given number of edges (Theorem 12), which will immediately imply the following result. Theorem 1. jPn jpn! ð37:3ÞnþoðnÞ : Theorem 12 will turn out to be an immediate consequence of a result of Tutte [8] on the number of planar triangulations and the following result, which states that the number of triangulations of every planar graph is exponential in the number of edges which are needed in order to triangulate the graph. We will prove this result in Section 3, where we will also see (Proposition 11) that the bound given in Theorem 2 is essentially best possible for mX2n: Theorem 2. Every labelled planar graph G with n vertices and m edges is contained in at least e3ð3nmÞ=2 labelled triangulations on n vertices, where e is an absolute constant. Combining our upper bounds with the result in [1] mentioned earlier, we will deduce the following result in the final section. Given a class A of graphs and a property Q; we say that almost all graphs in A have Q if the proportion of graphs in A on n vertices which have Q tends to one as n-N: Theorem 3. Almost all graphs in Pn have less than 2:56n edges.

2. Definitions and basic facts For convenience, for nAN we let ½n :¼ f1; y; ng: A plane graph is a planar graph together with an embedding into the plane. A planar graph G is called rigid if any two embeddings of G are equivalent. By the theorem of Whitney, every 3-connected

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

121

planar graph is rigid (see e.g. [3]). Given a face f ; we denote its boundary by bð f Þ: Moreover, if f is not the outer face, we say that the bounding cycle of f is the shortest cycle containing f in its interior and denote it by bcð f Þ: Note that bcð f ÞCbð f Þ and that we have equality if G is 2-connected. We say that a vertex x lies in f if xAbð f Þ: Given a face f ; we treat the boundary of f as an ordered sequence of not necessarily distinct vertices v1 ; y; vk : If ioj and vi avj are not adjacent, then the two sequences viþ1 ; y; vj1 and vjþ1 ; y; vk ; v1 ; y; vi1 are non-empty and we call them the left and the right vi -vj -side of f ; respectively. For a set of labelled graphs A; denote by Au the set of distinct unlabelled graphs contained in A; each representing an isomorphism class of A: Denote by An the set of those graphs in A with vertex set ½n and by An;m the set of those graphs in An with exactly m edges. Denote by P the set of all labelled planar graphs. We shall need a few classes of special planar graphs. Define T :¼ fGAP : jEðGÞj ¼ 3jV ðGÞj  6g: Thus T is the set of all maximal planar graphs. It is well known that in every embedding of a graph GAT all faces are bounded by triangles. Tutte [8] proved that 256 B9:48 ð1Þ jTun j ¼ ð1 þ oð1ÞÞCgn n5=2 ; where g ¼ 27 and where C is some positive constant. It is well known (see e.g. [5] for a proof) that the number of triangulations of the interior of an c-cycle is given by CatðcÞ; the cth Catalan number: ! 2c  4 1 CatðcÞ ¼ ð2Þ ¼ 4cþoðcÞ : c1 c2

3. Triangulating a planar graph The aim of this section is to prove Theorem 2. The basic idea is as follows. Consider a plane graph GAPn;m : We would like to generate as many triangulations containing G as possible, and the easiest way would be to simply triangulate each (non-triangular) face independently. This may of course not always be possible, because two non-adjacent vertices which are connected in order to triangulate one face can then not be connected in any of the neighbouring faces. It turns out (see Proposition 5) that this approach does work for 3-connected planar graphs. However, in general, in order to generate many triangulations, we have to make use of the different embeddings that a planar graph may have. For instance, the graph in Fig. 1 has only one triangulation when viewed as a plane graph but superexponentially many when viewed as a labelled planar graph. Before dealing with this, let us first consider the 3-connected case. We say that a planar graph has the 1-face property if it has an embedding so that the intersection of

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

122

Fig. 1. A plane graph with only one triangulation.

the boundaries of two faces consists of either an edge, a vertex or is empty. Equivalently, if x and y lie on the boundary of some face f and are not adjacent, then they do not both also lie on the boundary of some other face f 0 : Proposition 4. A 3-connected plane graph G has the 1-face property. This seems to be a folklore result (see e.g. [7]). As the proof is short, we include it here for completeness. We mention (but will not make use of this) that the converse is also true: a 2-connected graph which has the 1-face property must be 3-connected. Proof of Proposition 4. Suppose that G does not have the 1-face property. Then there exist vertices x and y which are contained in the boundaries of two faces f1 and f2 and where the edge xy (which may or may not be present in G) does not lie on the boundary of both faces. But this implies that there are two faces of G  xy into which we can insert the edge xy and thus that G þ xy does not have a unique embedding. By Whitney’s theorem, G þ xy cannot be 3-connected (and hence neither is G). & The above proposition implies that it is easy to prove Theorem 2 for 3-connected graphs. Proposition 5. Let G be a 3-connected plane graph in Pn;m : Then the number of triangulations on n vertices which contain G is at least 23nm6 : Proof. Using Proposition 4, it is easy to see that the number of triangulations of G is equal to the product (over all faces) of the number of triangulations of each face. To calculate the product, first note that the boundary of each face of G is a cycle, and so the number of triangulations of such a face f is given by the Catalan number CatðcÞ; where c is the length of the bounding cycle of f : Using (2), it is easy to show by induction that CatðcÞX2c3 for any cX3: Now denote by cj the length of the boundary of the jth face. Since every edge lies on the boundary of two faces, this gives us X cj ¼ 2m; ð3Þ j

where the sum is over all faces of G: Moreover, from Euler’s formula we know that there are 2  n þ m faces. Combining all this, the number of triangulations on n

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

123

vertices of G is Y j

Catðcj ÞX

Y

2cj 3 ¼ 2

P j

ðcj 3Þ

¼ 22m3ð2nþmÞ ¼ 23nm6 :

&

j

So we have proven that every 3-connected graph GAPn;m is contained in at least 2 triangulations. In other words, the deletion of an edge doubles the number of triangulations if the resulting graph is 3-connected. The above proof shows that this is tight if and only if all faces are triangles or quadrilaterals. Before we move closer towards the proof of Theorem 2, we make some preliminary steps (Propositions 6 and 7). We say that two planar graphs G0 ; G1 APn are incomparable if there is no planar graph HAPn containing both G0 and G1 as a subgraph. Obviously it is true that 3n6m

G0 DH0 ; G1 DH1 ; G0 and G1 are incomparable ) H0 and H1 are incomparable:

ð4Þ

(Here the Hi are allowed to have more vertices than the Gi :) For a planar graph G % so that G þ e is still planar. In denote by AddðGÞ the set of all edges eAEðGÞ contrast, for a plane graph G denote by InsðGÞ the set of those edges eAAddðGÞ; so that e can be inserted into the current embedding of G: Suppose that G and H are planar graphs. Then % GDH ) EðGÞ-EðHÞDAddðGÞ:

ð5Þ

Observe that for a rigid plane graph G we have that AddðGÞ ¼ InsðGÞ: Moreover, note that rigidity is not necessarily preserved when adding vertices and/or edges to a graph. On the other hand, every subdivision of a rigid graph is rigid, as this means nothing else than replacing edges by paths. In particular, every subdivision of a 3connected graph is rigid. The following actually rather obvious proposition will turn out to be useful. Suppose we have two plane graphs and the first one has an edge which the second one does not have and cannot have—given its present embedding. If the second one is rigid, then this means that it will never be able to get it, and therefore there is no third planar graph containing both of the two graphs. Proposition 6. Let G0 and G1 be two plane graphs with vertex set ½n where G1 is a subdivision of a 3-connected graph. If there exists an edge e0 AEðG0 Þ-EðG%1 Þ such that e0 eInsðG1 Þ; then G0 and G1 are incomparable. Proof. Suppose to the contrary that there is a planar graph HAPn containing G0 and G1 as subgraphs. Then e0 AEðHÞ; and applying (5) to G1 and H shows that e0 AAddðG1 Þ: On the other hand, G1 is rigid because it is a subdivision of a 3connected graph. Therefore AddðG1 Þ ¼ InsðG1 Þ: Hence e0 AInsðG1 Þ; contradicting the assumption. &

124

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

Stepping back from planarity for a moment, consider a graph G containing a triangle T: Suppose that fx; yg is a cut-set. Then there exists exactly one component H of G  x  y which contains all vertices in T\fx; yg and we call H the Tcomponent of G  x  y: Proposition 7. Let G be a graph which is 2-connected but not 3-connected and let T be a triangle in G: Let fx; yg be a cut-set of G which minimizes the cardinality of the Tcomponent H of G  x  y; and let H þ be the subgraph of G induced by V ðHÞ,fx; yg; where we only include the edge xy if xyAT: Then H þ is 2-connected. Proof. Suppose to the contrary that there exists a vertex z in H þ such that H þ  z has two components H1 and H2 : We can assume, without loss of generality, that xAH1 and yAH2 ; because if one of the Hi contains neither x nor y; then G  z would not be connected. As there are no edges between H1 and H2 ; this implies that xyeH þ ; and hence by definition of H þ ; xyeT: But then T must lie either in H1 þ z or in H2 þ z: Suppose (again without loss of generality) that TDH1 þ z: But then H1  x is a component of G  x  z which contains T\fx; zg; and so it is a Tcomponent which is smaller than H: & Returning to planar graphs, consider a plane 2-connected graph G whose outer face f is bounded by a triangle T: In this case we will refer to the T-component as the external component. Two paths are called internally disjoint if their intersection contains at most their endvertices. For two vertices u; w; a path denoted by Pðu; wÞ is a path connecting u and w: Now reconsider our position with respect to proving Theorem 2. Recall that if G is not 3-connected, then we cannot apply Proposition 5. Instead, we consider a cut-set fx; yg of G and consider the components H0 ; y; Hk of G  x  y: In Lemma 8, which constitutes the core of the proof of Theorem 2, we fix the embedding of H0 þ x þ y; and then embed all other components in several ways into that face of H0 þ x þ y which contains x and y: For every such embedding, we fix the positions of the Hi by inserting additional edges, so that the resulting graph is rigid as far as the relative positions of the Hi are concerned. Finally we make sure that the graphs obtained in this way are not only distinct but also incomparable—in other words, no matter how we later add more edges, the resulting graphs will continue to be distinct, so that in the end we really have the required number of distinct triangulations. Lemma 8. Let GAPn;m be a 2-connected plane graph whose outer face f is a triangle. Let fx; yg be a cut-set which minimizes the cardinality of the external component H0 : Suppose that G  x  y has k þ 1X2 components. Set t :¼ k if xyAG and t :¼ k þ 1 if xyeG: Then there is a family of pairwise incomparable plane graphs G1 ; y; Gs whose outer face is still f ; such that for all 1pips; the embeddings of the Gi and G are the same when restricted to V ðH0 Þ; Gi APn;mþt ;

GCGi ;

Gi  x  y is connected

and sX3t=2 : In the exceptional case where xyAf ; we only require that sX3ðt1Þ=2 :

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

125

Proof. Denote by H0 ; y; Hk the plane subgraphs of G which are induced by the connected components of G  x  y; where H0 is the external component. Denote by Hiþ the plane subgraph of G induced by V ðHi Þ,fx; yg; where we include the edge xy if and only if i ¼ 0 and xyAf : (By Proposition 7, this will imply that H0þ is 2connected.) For each iX1; it is clear that x and y lie in the outer face of Hiþ : As xyeHiþ for iX1; following the notation in the beginning of Section 2, we choose a shortest path Pi in Hi connecting the left and the right x-y-side of the outer face of Hiþ ; and let ci be the first and ri be the last vertex of Pi : If ci ari then in Hiþ there exist pairwise internally disjoint paths Pðci ; xÞ;

Pðri ; xÞ;

Pðci ; yÞ;

Pðri ; yÞ:

If jPi j ¼ 1 and ci ¼ ri ; then the respective paths above coincide. Case 1: xyeG: Consider H0þ : It is clear that there exists a face f 0 of H0þ such that x and y now lie on bð f 0 Þ: By Proposition 7, H0þ is 2-connected, so both x and y must lie in bcð f 0 Þ ¼ bð f 0 Þ: As xy is not contained in G and thus neither in H0þ ; this immediately implies that bð f 0 Þ has at least four vertices, and in particular f 0 af : Moreover, let P0 be a shortest path in H0 connecting the left and right x-y-side of bð f 0 Þ: P0 exists because H0 is connected. Denote by c0 ar0 the two endvertices of P0 : Observe that bð f 0 Þ-P0 ¼ fc0 ; r0 g: Similarly to the paths in Hiþ ; we divide bð f 0 Þ into four paths Pðc0 ; xÞ;

Pðr0 ; xÞ;

Pðc0 ; yÞ;

Pðr0 ; yÞ

which are all pairwise internally disjoint. Now choose a permutation s on ½k and an integer h from f0; y; k þ 1g: Given s and h; construct the graph Gs;h as follows. For convenience, set sð0Þ :¼ 0 and sðk þ þ into f 0 in such a way that the edge 1Þ :¼ 0: Successively, for every iA½k ; embed HsðiÞ rsði1Þ csðiÞ can be added (and add it). Having done this for all i; add the edge rsðkÞ c0 : Finally, if h40; remove the edge rsðh1Þ csðhÞ and insert the edge xy instead. Note that Gs;h has m þ t edges, where t ¼ k þ 1 as required. Moreover, we have constructed s :¼ k!ðk þ 2ÞX3

kþ1 2

t

¼ 32

graphs Gs;h : It is clear from the construction that each Gs;h is a plane graph whose outer face is identical to the outer face f of G and whose embedding when restricted to V ðH0 Þ is the same as that of G: Obviously, each Gs;h also contains G: As all components Hi of G  x  y are now connected by new edges, we also know that Gs;h  x  y is connected (Figs. 2 and 3). It remains to prove that the Gs;h are pairwise incomparable. To this end, we define two auxiliary graphs which are obtained from Gs;h as follows. We first define Bs;h DGs;h : For h ¼ 0; Bs;0 :¼

k[ þ1

ðrsði1Þ csðiÞ ,PsðiÞ ,PðcsðiÞ ; xÞ,PðrsðiÞ ; xÞ,PðcsðiÞ ; yÞ,PðrsðiÞ ; yÞÞ

i¼1

126

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

Fig. 2. Illustrating the proof of Lemma 8. The thick edges are the edges which are added to G to form Gs;h :

þ Fig. 3. The graphs Hsð1Þ and Hsð1Þ corresponding to the example in the previous figure.

and for h40; we obtain Bs;h from Bs;0 by removing the edge rsðh1Þ csðhÞ and inserting the edge xy instead. Observe that the vertices in Bs;h which have degree at least 3 are exactly x; y; c0 ; r0 ; y; ck ; rk : Now obtain As;h by successively contracting all paths between these vertices into edges. Alternatively, As;h can also be obtained from a complete bipartite graph with classes fx; yg and fc0 ; r0 ; y; ck ; rk g by adding either a Hamilton cycle to the second class (if h ¼ 0) or Hamilton paths to both classes (if h40). It is straightforward to check that As;h is 3-connected, and hence Bs;h is a subdivision of a 3-connected graph. We now show that the Bs;h are pairwise incomparable. By the construction of Bs;h (in particular, since Bs;h is rigid), it is clear that there is no edge ri cj AInsðBs;h Þ with iaj: Thus, when considering B ¼ Bs;h and B0 ¼ Bs0 ;h0 ; it suffices to find an edge ri cj AEðBÞ-EðB0 Þ with iaj in order to apply Proposition 6. If sas0 ; then kX2 and, recalling that sð0Þ ¼ s0 ð0Þ ¼ 0 and sðk þ 1Þ ¼ s0 ðk þ 1Þ ¼ 0; let iX1 be the smallest integer so that sðiÞas0 ðiÞ and let jpk be the largest integer so that sðjÞas0 ðjÞ: Note that ioj: Then rsði1Þ csðiÞ ; rsðjÞ csðjþ1Þ AEðBÞ-EðB0 Þ; unless they are removed from B before adding xy: But as at most one of them will be removed, we are done. If s ¼ s0 ; then rsðh0 1Þ csðh0 Þ AEðBÞ-EðB0 Þ: Thus the Bs;h are

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

127

pairwise incomparable, and hence by (4), so are the Gs;h : This completes the proof of the lemma for Case 1. Case 2a: xyAG; xyef : By definition, xyeH0þ ; so the only difference to Case 1 is that we need the edge xy to be present in all our graphs Gs;h ; in other words, we require that 1phpk þ 1; so that the total number of graphs is s :¼ k!ðk þ 1Þ when adding t :¼ k edges to G (one edge less as before, because xy already exists in G). Checking that k

t

s ¼ ðk þ 1Þ!X32 ¼ 32 completes this case. Case 2b: xyAG; xyAf : As xyAH0þ and H0þ is 2-connected, there are two faces in H0þ whose boundaries contain xy: Note that one of them is f ; and denote the other one by f 0 : Furthermore the face f 0 into which we will be embedding the other Hi is bounded by a cycle bð f 0 Þ containing x and y: However, as xyCbð f 0 Þ; we now cannot assume the existence of two vertices r0 and c0 on bð f 0 Þ to which we can connect the Hi as before. So we still proceed as in Case 1, except that we fix h :¼ k þ 1 and do not include c0 and P0 in Bs;kþ1 : (Nevertheless, it is easy to check that the resulting graphs As;kþ1 are still 3-connected.) Hence the total number of graphs is s :¼ k! when adding t :¼ k edges to G: By the statement of the lemma, this time we only need to check that s ¼ k!X3

k1 2

¼3

t1 2 :

As our construction is a special case of the general construction for Case 1, it is clear that the graphs constructed in this way fulfil all the requirements of the lemma. & Observe that we can apply Lemma 8 iteratively, so that starting from a 2connected graph G; we produce 3-connected graphs Gi satisfying the above requirements (once there are no more vertex pairs x and y to which we can apply the lemma, this means we have arrived at a graph which is 3-connected). We then apply Proposition 5 to the 3-connected graphs. So the only remaining problem is that we need to get started if G is not 2-connected. Roughly speaking, we solve this problem by simply embedding loose blocks into faces of 3-connected components and fixing them there. Recall that a block of a graph G is a maximal 2-connected component. The following definitions will be convenient. Given a rooted tree, we say that the children of a vertex v are those vertices which are adjacent to v and whose distance to the root is greater than that of v: Given a plane graph G; a triangulation tree of G is a rooted tree whose vertices correspond to plane graphs (with vertex set ½n ) containing G; whose root corresponds to G; whose leaves correspond to 3-connected graphs which are pairwise incomparable; for any vertex v of the tree, the graphs corresponding to the children of v all have the same number of edges and, finally, if a child has t more

128

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

edges than its parent v; then v has at least 3t=2 children unless it is an exceptional vertex, in which case it still has at least 3ðt2Þ=2 children. Observe that in our definition we require the leaves of the tree to be pairwise incomparable, however this is guaranteed via (4) if the children of each vertex are pairwise incomparable. Our aim will be to construct a triangulation tree of G with few exceptional vertices on any path from the root to a leaf. Lemma 9. Consider a plane graph GAPn;m consisting of a 3-connected plane graph G 0 (whose outer face is a triangle) and a block H which has exactly one vertex x in common with G0 : Then there is a triangulation tree of G with no exceptional vertices, unless x is contained in the boundary of the outer face of G and has degree at most six in G 0 ; in which case the root of the tree may be exceptional. Proof. Suppose first that x lies on the boundary of the outer face and has degree at most six. Let z be a vertex in H which is adjacent to x: Let y be a vertex on the boundary of the outer face which is adjacent to x and let v be a vertex which is not in the outer face but lies on the same face f as x and y in G0 (such a v exists since x has degree at least three in G0 ). Let G10 be the graph obtained from G by inserting the edges zy and zv (thus H is embedded into f —see Fig. 4). Now apply Lemma 8 to G10 : If the resulting graphs G1 ; y; Gs are not 3-connected, then we repeatedly apply Lemma 8 to those graphs and their children until we arrive at graphs which are 3connected. We claim that these graphs then form the leaves of a triangulation tree of G10 containing no exceptional vertices. In other words, we can never encounter the exceptional case Lemma 8 where the two cut-vertices lie in the outer face. This follows since G 0 is 3-connected and V ðHÞ\fxg is connected to two distinct vertices of G 0 in G10 : Thus we cannot separate the graph into several components by a cut consisting of exactly two vertices on the outer face. Since the vertices on the outer face are always the same, this proves the claim. We then obtain a triangulation tree of G by adding one more vertex (corresponding to G) and letting its only child be the vertex corresponding to G10 : Since G10 had two more edges than G; the root of this tree is an exceptional vertex. Now suppose that the degree of x in G 0 is more than six. Let v1 ; y; vp ; where pX7; be the neighbours of x in G 0 ; ordered clockwise when viewed from x: Then x has at

Fig. 4. Illustrating the proof of Lemma 9 where the block H is a triangle. The thick edges are those which were added to G:

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

129

least four neighbours y01 ; y; y04 (also ordered clockwise when viewed from x) which are not contained in the outer face. Let f1 be the face of G 0 which contains x; y01 and the neighbour vi of x which lies to the left of y01 when viewed from x: Then we may have vi ¼ y04 but we claim that f1 cannot also contain y02 or y03 : (Indeed, if f1 contains y02 for instance, then one can easily verify that the removal of x and y02 separates y01 from vi ; contradicting the fact that G 0 is 3-connected.) Now let f2 be the face of G 0 which contains x; y03 and the neighbour vj of x which lies to the left of y03 when viewed from x: Then as above, we may have vj ¼ y02 but y01 is not contained in f20 : Similarly, it is easily checked that there is no face f which contains x; y01 and y03 : Now let y1 :¼ y01 and y2 :¼ y03 : Let z be a vertex in H which is adjacent to x: For i ¼ 1; 2, let Gi be the graph obtained from G 0 by inserting H and the edges xz and zyi into fi : Obviously, Gi contains G (see Fig. 4). 0 Hence an application of Lemma 8 to Gi gives us graphs Gi1 ; y; Gis0 0 which contain G and which are incomparable. By repeatedly applying Lemma 8 to the graphs Gij0 obtained and their children, we will eventually obtain graphs Gi1 ; y; Gis which have the additional property of being 3-connected and which form the leaves of a triangulation tree of Gi : As in the previous case, there are no exceptional vertices. (Consider two vertices w1 and w2 on the outer face of Gi and let W :¼ fw1 ; w2 g: Since fi was not the outer face, we have V ðHÞ-W Dfxg: Since H is 2-connected, it follows that H  W is connected. Also, since the yi are not contained in the outer face, we have yi eW and thus Gi  W contains the edge zyi : Finally, since G0 is 3-connected, G 0  W is connected. Putting these three observations together, we see that Gi  W is connected.) We will now prove that for any j; G1j is incomparable with G2 (and thus with G2j0 ; for any j 0 ). For this, by applying Proposition 6 with e0 ¼ zy2 ; it suffices to show that zy2 AEðG2 Þ-EðG1j Þ and zy2 eInsðG1j Þ: To see this, first note that as G 0 is 3connected and contains the outer face, in any of the above applications of Lemma 8, G0 will be contained in the external component and thus the embeddings of G1j when restricted to G 0 will be the same as that of G2 when restricted to G 0 : Now consider the embedding of G1j when restricted to G 0 þ z: G 0 þ z contains both zy1 and zx; so z must be embedded into a face of G 0 containing both x and y1 : Since G 0 contains no face which contains x and both of the yi ; this means that zy2 eEðG1j Þ and zy2 eInsðG1j Þ and thus the conditions of the proposition are satisfied. Since xzAG; the Gi have only one more edge than G and we thus obtain a triangulation tree of G (with no exceptional vertices) as follows. We form a single tree from the triangulation trees of the Gi by adding a root vertex corresponding to G and letting its two children correspond to the Gi : & We can now prove Theorem 2 for connected graphs. Theorem 10. Every connected planar graph GAPn;m is contained in at least d3ð3nmÞ=2 labelled triangulations, where d is an absolute constant.

130

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

Proof. By inserting at most two edges into G; we can obtain a graph G 0 that has a block B which contains a triangle and which contains at least four vertices. Our aim is to construct a triangulation tree whose root corresponds to G0 and whose vertices correspond to graphs obtained from repeated applications of Lemmas 8 and 9 (and so contain G 0 ). Fix an embedding of B so that the outer face is a triangle. If B is not 3-connected, we apply Lemma 8 to obtain a set of children of B: We then apply Lemma 8 to those children which are not 3-connected and continue in this way until we have obtained a triangulation tree of B whose root corresponds to B; where the remaining vertices correspond to descendants of B and whose leaves are B1 ; y; Bs ; say. Note that we do not assume that the graphs corresponding to the leaves all have the same number of edges. Also on any path from the vertex to the root of this tree, the number of exceptional vertices is at most three—they can only appear if we apply the lemma to a pair of vertices on the outer face and the vertices on the outer face are always the same. If B ¼ G 0 (i.e. G 0 was 2-connected), then we have a triangulation tree of G0 : Now suppose that G0 was not 2-connected and let H be a block of G0 which has a vertex x in common with B (there will be exactly one such vertex in H). Now apply Lemma 9 to the graphs Bi þ H to obtain triangulation trees of Bi þ H: We merge these into a single triangulation tree of B,H as follows: we start with the triangulation tree of B except that a vertex of the tree which corresponded to a graph F in the triangulation tree of B now corresponds to F þ H: We then identify the roots of the triangulation trees of Bi þ H with the leaves Bi of the tree of B: If B þ H ¼ G 0 ; then again we have a triangulation tree of G 0 : If this is not the case, we take a new block H 0 and apply Lemma 9, until we have dealt with all the blocks of G 0 and thus obtained a triangulation tree of G 0 : It is now easy to verify by backward induction on the distance from the root in the triangulation tree that each graph corresponding to a vertex of the tree is contained in the required number of triangulations. By Proposition 5, this is certainly true (with d ¼ 26 ) for the leaves of the tree because they are 3-connected. For the induction step, consider a vertex F APn;m and suppose that its children all have m þ t edges and are all contained in at least q triangulations. Then Lemmas 8 and 9 imply that the number of triangulations of F is at least q3t=2 (which is exactly what we are aiming for), unless we encountered the exceptional case of either of the lemmas, in which case we find at least q3ðt2Þ=2 triangulations. But it is easily seen that on any path from a leaf to the root of the tree we can encounter the exceptional case of Lemma 8 at most three times when we build a triangulation tree of B: When we apply Lemma 9 to incorporate the other blocks, we can encounter the exceptional case (where x lies on the outer face and has degree at most six) at most 12 times altogether (since an application of the lemma increases the degree of the vertex x in the statement of the lemma by at least one and there are three vertices on the outer face, which are always the same ones). Since G 0 had at most two more edges than G; this proves the theorem (rather crudely) with d ¼ 3ð2=2þ3þ12Þ 26 : &

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

131

Finally, we are in a position to deal with the case where G is not necessarily connected. Proof of Theorem 2. If G has a component K containing all but at most two vertices of G; then we are immediately done by applying Theorem 10 to C: So suppose that this is not the case. By inserting at most six edges into G; we can obtain a graph G 0 which contains two triangles ta and tb which are both contained in distinct components. Let va be a vertex on ta and vb one on tb : Denote by K1 ; y; Kk the components of G 0 not containing ta or tb : We now construct 2k connected plane graphs Gs which all contain G 0 as a subgraph. Consider some s with 0pso2k and consider the binary expansion of s: If the cth entry is equal to 0, we place the Kc into ta and add an edge joining Kc to va : If the cth entry is equal to 1, we do the same with tb instead. Carrying this out for all c with 1pcpk; this gives us a plane graph Gs : Thus for each 0pio2k ; the graph Gi has two components Ai and Bi with ni;a and ni;b vertices and mi;a and mi;b edges respectively (where ni;a þ ni;b ¼ n and mi;a þ mi;b pm þ 6 þ k) and an embedding so that the outer face is bounded by ta and tb : Now we apply Theorem 10 to all the Ai and Bi : Clearly, we can turn any triangulation Ti;a of Ai and Ti;b of Bi into one of Gi by considering an embedding of Ti;a and Ti;b where ta and tb are on the outer face and triangulating the outer face of the resulting plane graph in an arbitrary way (we call such triangulation of Gi a canonical triangulation of Gi ). Since in the last step we only added edges which have one endpoint in ta and the other in tb ; the number of canonical triangulations of Gi is at least the product of the number of triangulations of Ai and Bi : Finally, we claim that for any 0piajo2k ; any canonical triangulation T of Gi is incomparable with Gj : Indeed, since iaj; there must be an c so that Kc was inserted into tb (by adding an edge eb between vb and Kc ) in Gj but not in Gi : The claim now follows by applying Proposition 6 to eb ; Gj and T: Theorem 10 now shows that the number of triangulations of G 0 is at least k 2X 1

d2 3ð3ni;a mi;a þ3ni;b mi;b Þ=2 X2k d2 3ð3nm6kÞ=2 ¼

i¼0

as required.

 d2 ð3nmÞ=2 2 k pffiffiffi 3 33 3

&

We conclude this section by showing that Theorem 2 is essentially best possible for mX2n: Proposition 11. For any c with 2pcp3 and for all nAN; there is a graph G in Pn0 ;m ; where n0 ¼ n þ oðnÞ and m ¼ cn þ oðnÞ; so that the number of triangulations on n0 0 vertices which contain G is 3ð3n mþoðnÞÞ=2 :

132

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

Proof. We construct G as follows. We begin with a square grid on n=2 þ oðnÞ vertices together with an arbitrary triangulation of the outer face of the grid (the number of edges needed to triangulate the outer face is oðnÞ) to obtain a plane graph D: Since we are considering labelled plane graphs, we can speak of the ‘‘top row’’ of the grid, etc. in what follows. We now ‘‘augment’’ each square inside the grid by adding a single new vertex into each face of the square grid and connecting it to both the bottom left and the top right vertex of the face (in other words, an augmented square is a four-cycle where two opposite vertices are connected by an additional path of length two). The resulting graph has n þ oðnÞ vertices, 2n þ oðnÞ edges and n=2 þ oðnÞ augmented squares. We obtain a graph G with m ¼ cn þ oðnÞ edges by selecting ðc  2 þ oð1ÞÞn=2 squares of the original grid and connecting the corresponding new vertices inside these squares to the remaining two vertices on the outside of this square. We call an augmented square not triangulated in this way open. It remains to verify the claim about the number of triangulations of G: Since D is 3-connected, Proposition 4 implies that D has the 1-face property (which can of course also be easily verified directly). Hence, as already noted at the beginning of the proof of Proposition 5, the number of triangulations of D is the product of the number of triangulations of the squares in D: It is easily seen that this in turn implies that the number of triangulations of G is the product of the number of triangulations of the open augmented squares. But, clearly, the number of triangulations of each open augmented square is exactly three and there are n m  2n 3n  m  þ oðnÞ ¼ þ oðnÞ 2 2 2 open squares.

&

4. Upper bounds In this section, we apply Theorem 2 to deduce upper bounds on the number of planar graphs (implying Theorem 1) and on their likely number of edges (Theorem 3). For 0oxo1 let HðxÞ :¼ x log x  ð1  xÞ logð1  xÞ

ð6Þ

be the entropy function, where log denotes the logarithm to base 2 and n let Hð0Þ :¼ Hð1Þ :¼ 0 for convenience. It has the property that ðxn Þ ¼ 2HðxÞnþoðnÞ for 0pxp1: For GAPn define bðGÞ :¼ jfHATn :GDHgj: For 0pcp3 we let bðc; nÞ :¼ min bðGÞ: GAPn;cn

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

133

By result (1) of Tutte, the number jTn j of labelled triangulations on n vertices is at most n! gnþoðnÞ : This implies that ! 3n  6 cn 23Hðc=3ÞnþoðnÞ pn! gnþoðnÞ jPn;cn jpjTn j : ð7Þ bðc; nÞ bðc; nÞ Theorem 2 implies that bðc; nÞX3ð3cÞn=2þoðnÞ and thus has the following immediate consequence, which is a generalization of Theorem 1. Theorem 12. For 0pcp3; jPn;cn jpn! gnþoðnÞ 23Hðc=3Þn 3ð3cÞn=2 : In particular, jPn jpn! ð37:3ÞnþoðnÞ (the maximum is attained at cB1:902) (see Fig. 5). Now we turn to the proof of Theorem 3, which stated that almost all graphs in Pn have at most 2:56n edges. Let P2 denote the set of 2-connected planar graphs. In the proof, we will employ the bound jPn jXjP2n j ¼ n! anþoðnÞ ; where aB26:1876; due to Bender et al. [1]. Proof of Theorem 3. Numerical calculation gives that g23Hðc=3Þ 3ð3cÞ=2 o26:18  0:1 for c ¼ 2:56: Note that this inequality also holds for cX2:56 as 23Hðc=3Þ 3c=2 is decreasing in this range. Thus if we apply Theorem 12 with cX2:56; we have [ jPn;m jpn! 0:44nð26:18  0:1ÞnþoðnÞ ¼ oðjPn jÞ; 2:56npmp3n6

which implies the result.

&

Our upper bound in Theorem 12 applies only to labelled graphs. However, since any unlabelled graph on n vertices corresponds to at most n! labelled graphs the nþoðnÞ above result of [1] immediately implies that jPun jXjP2;u : Similarly to n jXð26:18Þ

35 30 25 20 15 10 5 0.5

1

Fig. 5. The upper bound on jPn;cn j

1.5 1=n

2

2.5

3

=n! in Theorem 12 versus c; where 0pcp3:

134

D. Osthus et al. / Journal of Combinatorial Theory, Series B 88 (2003) 119–134

the proof of Theorem 3, one can compare this with the upper bound ! u nþoðnÞ 3n  6 jPn;cn jpg cn

ð8Þ

(which follows from (1) again) to observe the following result. Theorem 13. Almost all graphs in Pun have at most 2:69n edges. * * Note added in proof: Several discussions with T. Luczak and A. Steger yielded a construction (based on the result of Bender et al.) which shows that jPn jXn!27:29nþoðnÞ : In particular, the probability that a random planar graph is 2connected is exponentially small. Using this lower bound instead of that of Bender et al. in the proof of Theorem 3 would slightly improve the bound on the number of edges of almost all planar graphs from 2:56n to 2:522n: For more details, See Lo¨ffler (Studienarbeit, HU Berlin).

References [1] [2] [3] [4] [5] [6] [7] [8]

A. Bender, Z. Gao, N.C. Wormald, The number of labeled 2-connected planar graphs, preprint, 2000. A. Denise, M. Vasconcellos, D. Welsh, The random planar graph, Congr. Numer. 113 (1996) 61–79. R. Diestel, Graph Theory, Springer, Berlin, 1997. S. Gerke, C. McDiarmid, On the number of edges in random planar graphs, to appear in Combinatorics, Probability and Computing. L. Lova´sz, Combinatorial Problems and Exercises, 2nd Edition, North-Holland, Amsterdam, 1993. C. McDiarmid, A. Steger, D. Welsh, Random planar graphs, preprint, 2001. R.C. Mullin, P.J. Schellenberg, The enumeration of c-nets via quadrangulations, J. Combin. Theory 4 (1968) 259–276. W.T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962) 21–38.