Printer Friendly
The Free Library
22,728,043 articles and books

Degree distribution in random planar graphs.



We prove that for each k [greater than or equal to] 0, the probability that a root vertex A corner point of a triangle or other geometric image. Vertices is the plural form of this term. See vertex shader.  in a random planar graph In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. A nonplanar graph cannot be drawn in the plane without edge intersections.  has degree k tends to a computable constant [d.sub.k], and moreover that [summation summation n. the final argument of an attorney at the close of a trial in which he/she attempts to convince the judge and/or jury of the virtues of the client's case. (See: closing argument) .sub.k][d.sub.k] = 1. The proof uses the tools developed by Gimenez and Noy in their solution to the problem of the asymptotic enumeration 1. (mathematics) enumeration - A bijection with the natural numbers; a counted set.

Compare well-ordered.
2. (programming) enumeration - enumerated type.
 of planar A technique developed by Fairchild Instruments that creates transistor sublayers by forcing chemicals under pressure into exposed areas. Planar superseded the mesa process and was a major step toward creating the chip.  graphs, and is based on a detailed analysis of the generating functions involved in counting planar graphs. However, in order to keep track of the degree of the root, new technical difficulties arise. We obtain explicit, although quite involved expressions, for the coefficients in the singular expansions of interest, which allow us to use transfer theorems This is a list of theorems, by Wikipedia page. See also
  • list of fundamental theorems
  • list of lemmas
  • list of conjectures
  • list of inequalities
  • list of mathematical proofs
  • list of misnamed theorems
  • Existence theorem
 in order to get an explicit expression for the probability generating function p(w) = [summation.sub.k][d.sub.k][w.sup.k]. From the explicit expression for p(w) we can compute the [d.sub.k] to any degree of accuracy, and derive asymptotic estimates for large values of k.

Keywords: Planar graph, Random graph In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs. , Degree distribution.

1 Introduction

In this paper all graphs are simple and labelled with labels {1, 2, ..., n}. As usual, a graph is planar if it can be embedded Inserted into. See embedded system.  in the plane without edge crossings. A planar graph together with a particular embedding 1. (mathematics) embedding - One instance of some mathematical object contained with in another instance, e.g. a group which is a subgroup.
2. (theory) embedding - (domain theory) A complete partial order F in [X -> Y] is an embedding if
 in the plane is called a map. There is a rich theory of counting maps, and part of it is needed later on. However, in this paper we consider planar graphs as combinatorial objects, regardless of how many non-equivalent topological to·pol·o·gy  
n. pl. to·pol·o·gies
1. Topographic study of a given place, especially the history of a region as indicated by its topography.

2.
 embeddings they may have.

Random planar graphs were introduced by Denise et al. (7), and since then they have been widely studied. Let us first recall the probability model. Let [G.sub.n] be the family of (labelled) planar graphs with n vertices The plural of vertex. See vertex. . A random planar graph [R.sub.n] is a graph drawn from [G.sub.n] with the uniform distribution, that is, all planar graphs with n vertices have the same probability of being chosen. As opposed to the classical Erdos-Renyi model, we cannot produce a random planar graph by drawing edges independently. In fact, our analysis of random planar graphs relies on exact and asymptotic counting.

Several natural parameters defined on [R.sub.n] have been studied, starting with the number of edges, which is probably the most basic one. Partial results where obtained in (7; 12; 21; 5), until it was shown by Gimenez and Noy (13) that the number of edges in random planar graphs obeys asymptotically a normal limit law with linear expectation and variance. The expectation is asymptotically [kappa Kappa

Used in regression analysis, Kappa represents the ratio of the dollar price change in the price of an option to a 1% change in the expected price volatility.

Notes:
Remember, the price of the option increases simultaneously with the volatility.
]n, where [kappa] [approximately equal to] 2.21326 is a well-defined analytic constant. This implies that the average degree of the vertices is 2[kappa] [approximately equal to] 4.42652.

McDiarmid et al. (18) showed that with high probability a planar graph has a linear number of vertices of degree k, for each k [greater than or equal to] 1. Our main result is that for each k [greater than or equal to] 1, the expected number of vertices of degree k is asymptotically [d.sub.k]n, for computable constants [d.sub.k] [greater than or equal to] 0. This is equivalent to saying that the probability that a fixed vertex, say vertex 1, has degree k tends to a limit [d.sub.k] as n goes to infinity. In Theorem theorem, in mathematics and logic, statement in words or symbols that can be established by means of deductive logic; it differs from an axiom in that a proof is required for its acceptance.  6.9 we show that this limit exists and we give an explicit expression for the probability generating function

p(w) = [summation over (k [greater than or equal to] 1) [d.sub.k][w.sup.k],

from which the coefficients [d.sub.k] can be computed to any degree of accuracy. Moreover, we show that p(w) is indeed a probability generating function, that is, [summation][d.sub.k] = 1.

The proof is based on a detailed analysis of the generating functions involved in counting planar graphs, as developed in (13), where the long standing problem of counting planar graphs asymptotically was solved. However, in this case we need to keep track of the degree of a root vertex, and this makes the analysis considerably more difficult.

Here is a sketch of the paper. After some preliminaries, we obtain the degree distribution in simpler families of planar graphs: outerplanar graphs (Section 3) and series-parallel graphs (Section 4). These results are interesting on their own and pave PAVE Cardiology A clinical trial–Post AV Node Ablation Evaluation  the way to the more complex analysis of general planar graphs. We remark that the degree distribution in these simpler cases has been obtained independently in (3) using different techniques.

In Section 5 we compute the generating function of 3-connected maps taking into account the degree of the root, which is an essential piece in proving the main result. We rely on a classical bijection between rooted maps and rooted quadrangulations (6; 19), and again the main difficulty is to keep track of the root degree. The task is completed in Section 6, which contains the analysis for planar graphs. First we have to obtain a closed form for the generating function [B.sup.[*](x, y, w) of rooted 2-connected planar graphs, where x marks vertices, y edges, and w the degree of the root: the main problem we encounter here is solving a differential equation differential equation

Mathematical statement that contains one or more derivatives. It states a relationship involving the rates of change of continuously changing quantities modeled by functions.
 involving algebraic 1. (language) ALGEBRAIC - An early system on MIT's Whirlwind.

[CACM 2(5):16 (May 1959)].
2. (theory) algebraic - In domain theory, a complete partial order is algebraic if every element is the least upper bound of some chain of compact elements.
 functions and other functions defined implicitly. The second step is to obtain singular expansions of the various generating functions near their dominant singularities; this is particularly demanding, as the coefficients of the singular expansions are rather complex expressions. Finally, using a technical lemma lemma (lĕm`ə): see theorem.

(logic) lemma - A result already proved, which is needed in the proof of some further result.
 on singularity (1) See technology singularity.

(2) (Singularity) An experimental operating system from Microsoft for the x86 platform written almost entirely in C#, a .NET managed code language. Released in 2007, Singularity is a non-Windows research project.
 analysis and composition of singular expansions, we are able to work out the asymptotics for the generating function [C.sup.[*](x, y, w) of rooted connected planar graphs, and from this the probability generating function can be computed exactly. We also compute the degree distribution for 3-connected and 2-connected planar graphs, and for planar graphs according to according to
prep.
1. As stated or indicated by; on the authority of: according to historians.

2. In keeping with: according to instructions.

3.
 the edge density.

For each of the three families studied we obtain an explicit expression for the probability generating function p(w) = [summation.sub.k [greater than or equal to] 1][d.sub.k][w.sup.k], of increasing complexity. Theorems 3.2, 4.3 and 6.9 give the exact expressions in each case. The following tables show the approximate values for small values of k, and the asymptotic behaviour for large k. It is worth noticing that the shape of the asymptotic estimates for planar graphs agrees with the general pattern for the degree distribution in several classes of maps (15), where maps are counted according to the number of edges.

McDiarmid and Reed (17) have shown that the maximum degree in random planar graphs is [THETA](log n). From the asymptotic results in Theorem 6.9 we are led to conjecture CONJECTURE. Conjectures are ideas or notions founded on probabilities without any demonstration of their truth. Mascardus has defined conjecture: "rationable vestigium latentis veritatis, unde nascitur opinio sapientis;" or a slight degree of credence arising from evidence too weak or too  that if [[DELTA].sub.n] denotes the maximum degree in random planar graphs, then the expected value Expected value

The weighted average of a probability distribution. Also known as the mean value.
 is asymptotically

E[[DELTA].sub.n] ~ log n/log(1/q),

where q is as in Theorem 6.9. We remark that an analogous result holds for planar maps (11), counted according to the number of edges.

Let us mention that in a companion paper (8), we prove a central limit theorem central limit theorem

In statistics, any of several fundamental theorems in probability. Originally known as the law of errors, in its classic form it states that the sum of a set of independent random variables will approach a normal distribution regardless of the
 for the number of vertices of degree k in outerplanar and series-parallel graphs, together with strong concentration results. It remains an open problem to show that this is also the case for planar graphs. Our results in the present paper show that the degree distribution exists and can be computed explicitly. For lack of space we omit o·mit  
tr.v. o·mit·ted, o·mit·ting, o·mits
1. To fail to include or mention; leave out: omit a word.

2.
a. To pass over; neglect.

b.
: proofs; the coefficients of singular expansions; and the degree distribution for 2-connected graphs in each case, as well as for 3-connected planar graphs.

2 Preliminaries

For background on generating functions associated to planar graphs, we refer to (13) and (4), and to (20) for a less technical description. For background on singularity analysis of generating functions, we refer to the (9) and to the forthcoming book by Flajolet and Sedgewick (10).

For each class of graphs under consideration, [c.sub.n] and [b.sub.n] denote de·note  
tr.v. de·not·ed, de·not·ing, de·notes
1. To mark; indicate: a frown that denoted increasing impatience.

2.
, respectively, the number of connected and 2-connected graphs on n vertices. For the three graphs classes under consideration, outerplanar, series-parallel, and planar, we have both for [c.sub.n] and [b.sub.n], estimates of the form

c x [n.sup.-[alpha]][[rho].sup.-n]n!, (1)

where c, [alpha] and [rho] are suitable constants (4; 13). For outerplanar and series-parallel graphs we have [alpha] = -5/2, whereas for planar graphs [alpha] = -7/2. A general methodology for graph enumeration Graph enumeration is a subject of graph theory that deals with the problems of the following type: find how many non-isomorphic graphs have a given property.

See Pólya enumeration theorem for examples.
 explaining these critical exponents has been developed in (14).

We introduce the exponential 1. (mathematics) exponential - A function which raises some given constant (the "base") to the power of its argument. I.e.

f x = b^x

If no base is specified, e, the base of natural logarthims, is assumed.
2.
 generating functions C(x) = [summation][c.sub.n][x.sup.n]/n! and B(x) = [summation][b.sub.n][x.sup.n]/n!. Let [C.sub.k] be the exponential generating function (GF for short) for rooted connected graphs, where the root bears no label and has degree k; that is, the coefficient [[x.sup.n]/n!][C.sub.k](x) equals the number of rooted connected graphs with n + 1 vertices, in which the root has no label and has degree k. Analogously we define [B.sub.k] for 2-connected graphs. Also, let

[B.sup.*](x, w) = [summation][B.sub.k](x)[w.sup.k], [C.sup.*](x, w) = [summation][C.sub.k](x)[w.sup.k].

Notice that [C.sup.*](x, 1) = C'(x).

A basic property shared by the classes of outerplanar, series-parallel and planar graphs is that a connected graph (mathematics) connected graph - A graph such that there is a path between any pair of nodes (via zero or more other nodes).

Thus if we start from any node and visit all nodes connected to it by a single edge, then all nodes connected to any of them, and so on, then we will
 G is in the class if and only if the 2-connected components of G are also in the class. As shown in (13), this implies the basic equation

C'(x) = [e.sup.B'(xC'(x))]

between univariate GFs. If we introduce the degree of the root, then the equation becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII ASCII or American Standard Code for Information Interchange, a set of codes used to represent letters, numbers, a few symbols, and control characters. Originally designed for teletype operations, it has found wide application in computers. ] (2)

The reason is that only the 2-connected components containing the root vertex contribute to its degree.

Our goal in each case is to estimate [[x.sup.n]][C.sub.k](x), since the limit probability that a given fixed vertex has degree k is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

A first observation is that the asymptotic degree distribution is/ the same for connected members of a class than for all members in the class. Let G(x) be the GF for all members in the class, and let [G.sub.k](x) be the GF of all rooted graphs in the class, where the root has degree k. Then we have

G(x) = [e.sup.C(x)], [G.sub.k](x) = [C.sub.k](x)[e.sup.C(x)].

The first equation is standard, and in the second equation the factor [C.sub.k](x) corresponds to the connected component containing the root, and the second factor to the remaining components. The functions G(x) and C(x) have the same dominant singularity. Given the singular expansions of G(x) and C(x) at the dominant singularity in each of the cases under consideration, it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, in each case we only need to determine the degree distribution for connected graphs. A more intuitive explanation is that the largest component in random planar graphs eats up almost everything: the expected number of vertices not in the largest component is constant (16).

Another observation is that [d.sub.0] = 0 and [d.sub.1] = [rho], where [rho] is the constant appearing in the estimate (1) for [c.sub.n]; as we are going to see, [rho] is the radius of convergence In mathematics, the radius of convergence of a power series is a non-negative quantity, either a real number or that represents a range (within the radius) in which the function will converge.  of C(x). Indeed, there are no vertices of degree zero in a connected graph, and the proportion of rooted connected graphs in which the root has degree one is n(n - 1)[c.sub.n-1]/n[c.sub.n] ~ [rho].

The general approach we use for computing the [d.sub.k] is the following. Let f(x) = xC'(x) and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where w is considered as a parameter. Let also [rho] be the radius of convergence of C(x), which is the same as that of f(x). According to (2) we have to estimate [[x.sup.n]]H(f(x)), and this will depend on the behaviour of H(z) at z = f([rho]). In the outerplanar and series-parallel cases, H(z) turns out be analytic at f([rho]), whereas in the planar case we have a critical composition scheme, that is, the dominant singularity of H(z) is precisely f([rho]). This is a fundamental difference and we have to use different tools accordingly. Another difference is that [B.sup.*] is much more difficult to determine for planar graphs.

3 Outerplanar graphs

We start by recalling some results from (4). From the equivalence between rooted 2-connected outerplanar graphs and polygon polygon, closed plane figure bounded by straight line segments as sides. A polygon is convex if any two points inside the polygon can be connected by a line segment that does not intersect any side. If a side is intersected, the polygon is called concave.  dissections where the vertices are labelled 1, 2, ..., n in clockwise clock·wise  
adv. & adj. Abbr. cw.
In the same direction as the rotating hands of a clock.


clockwise
Adverb, adj

in the direction in which the hands of a clock rotate
 order (see Section 5 in (4) for details), we have the explicit expression

B'(x) = 1 + 5x - [square root of 1 - 6x + [x.sup.2]]/8.

The radius of convergence of B(x) is 3 - 2[square root of 2], the smallest positive root of 1 - 6x + [x.sup.x] = 0. The radius of convergence of C(x) is [rho] = [psi PSI - Portable Scheme Interpreter ]([tau]), where [psi](u) = u[e.sup.-B'(u)], and [tau] is the unique positive root of [psi]'(u) = 0. Notice that [tau] satisfies [tau]B"([tau]) = 0. The approximate values are [tau] [approximately equal to] 0.17076 and [rho] [approximately equal to] 0.13659. We also need the fact that [psi] is the functional inverse (mathematics) inverse - Given a function, f : D -> C, a function g : C -> D is called a left inverse for f if for all d in D, g (f d) = d and a right inverse if, for all c in C, f (g c) = c and an inverse if both conditions hold.  of xC'(x), so that [tau] = [rho]C'([rho]).

Let

D(x) = 1 + x - [square root of 1 - 6x + [x.sup.2]/4 (4)

and let [D.sub.k](x) = x[(2D(x) - x).sup.k-1] ([D.sub.k] is the ordinary GF for polygon dissections in which the root vertex has degree k). Then we have

[B.sub.k] = 1/2 [D.sub.k], k [greater than or equal to] 2, [B.sub.1] = x.

By summing a geometric series geometric series
n.
An infinite series of the form a + ax + ax2 + ax3 + . . .

Noun 1.
 we have an explicit expression for [B.sup.*], namely

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

Our goal is to analyze [B.sup.*](x, w) and [C.sup.*](x, w) = exp exp
abbr.
1. exponent

2. exponential
([B.sup.*](xC'(x),w)). For this we need the following technical lemma.

Lemma 3.1 Let f(x) = [[summation].sub.n [greater than equal to] 0][a.sub.n][x.sup.n]/n! denote the exponential generating function of a sequence [a.sub.n] of non-negative real numbers and assume that f(x) has exactly one dominating square-root singularity at x = [rho] of the form

f(x) = g(x) - h(x)[square root of 1 - x/[rho]],

where g(x) and h(x) are analytic at x = [rho] and f(x) has an analytic continuation In complex analysis, a branch of mathematics, analytic continuation is a technique to extend the domain of definition of a given analytic function. Analytic continuation often succeeds in defining further values of a function, for example in a new region where an infinite series  to the region {x [member of] C : [absolute value of x] < [rho] + [epsilon]} \ { x [member of] R : x [greater than or equal to] [rho]} for some [epsilon] > 0. Further, let H(x, z) denote a function that is analytic for [absolute value of x] < [rho] + [epsilon] and [absolute value of z] < f([rho]) + [epsilon] such that [H.sub.z]([rho], f([rho])) [not equal to] 0. Then the function

[f.sub.H](x) = H(x, f(x))

has a power series expansion [f.sub.H](x) = [[summation].sub.n [greater than or equal to] 0][b.sub.n][x.sup.n]/n! and the coefficients [b.sub.n] satisfy

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Applying the previous lemma with f(x) = B'(x) and H(x, z) = xw + x[w.sup.2]/2 4z-3x/1-(4z-3x)w, we obtain the following.

Theorem 3.2 Let [d.sub.k] be the limit probability that a vertex of a connected outerplanar graph has degree k then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [B.sup.*] is given by Equations (4) and (5).

Moreover p(1) = 1, so that the [d.sub.k] are indeed a probability distribution Probability distribution

A function that describes all the values a random variable can take and the probability associated with each. Also called a probability function.


probability distribution 
 and we have asymptotically, as K [right arrow] [infinity]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [c.sub.1], [c.sub.2] are suitable constants, and q = 2D([tau]) - [tau] [approximately equal to] 0.3808138.

4 Series-parallel graphs

First we recall the necessary results from (4). The radius of convergence of C(x) is, as for outerplanar graphs, [rho] = [psi]([tau]), where [psi](u) = u[e.sup.-B'(u)], and [tau] is the unique positive root of [psi]'(u) = 0. Again we have that [psi] is the functional inverse of xC'(x), so that [tau] = [rho]C'([rho]), and [tau] satisfies [tau]B"([tau]) = 0. The approximate values are [tau] [approximately equal to] 0.12796 and [rho] [approximately equal to] 0.11021.

In order to study 2-connected series-parallel graphs, we need to consider series-parallel networks, as in (4). We recall that a network is a graph with two distinguished vertices, called poles, such that the multigraph obtained by adding an edge between the two poles is 2-connected. Let D(x, y, w) be the exponential GF of series-parallel networks, where x, y, w mark, respectively, vertices, edges, and the degree of the first pole. Define S(x, y, w) analogously for series networks. Then we have

D(x, y, w) = (1 + yw)[e.sup.s(x,y,w)] - 1

S(x, y, w) = (D(x, y, w) - S(x, y, w)) xD(x, y, 1),

The first equation reflects the fact that a network is a parallel composition of series networks, and the second one the fact that a series network is obtained by connecting a non-series network with an arbitrary network (see (22) for details); the factor D(x, y, 1) appears because we only keep track of the degree of the first pole.

Remark. For the results of the present section, we do not need to take into account the number of edges and we could set y = 1 everywhere. However, in the case of planar graphs we do need the GF according to all three variables and it is convenient to present already here the full development. In the proof of the main result of this section, Theorem 4.3, we just set y = 1.

Set E(x, y) = D(x, y, 1), the GF for series-parallel networks without marking the degree of the root, which satisfies (see (4)) the equation

log(1 + E(x, y)/1 + y) = xE[(x, y).sup.2]/1 + xE(x, y). (7)

It follows that

log(1 + D(x, y, w)/1 + yw) = xE(x, y)D(x, y, w)/1 + xE(x, y). (8)

We also have the following relation between the [B.sub.k] and S.

Lemma 4.1

w[partial derivative][B.sup.*](x, y, w)/[partial derivative]w = [summation over k [greater than or equal to] 1]k[B.sub.k](x, y)[w.sup.k] = xyw[e.sup.S(x,Y,w)].

?From the previous equation it follows that

[B.sup.*](x, y, w) = xy [integral] [e.sup.S(x, y, w)]dw. (9)

Our next task is to get rid of the integral and to express [B.sup.*] in terms of D. Recall that E(x, y) = D(x, y, 1).

Lemma 4.2 The generating function of rooted 2-connected series parallel graphs is equal to

[B.sup.*](x, y, w) = x(D(x, y, w) - xE(x, y)/1 + xE(x, y) D(x, y, w) (1 + D(x, y, w)/2)).

Theorem 4.3 Let [d.sub.k] be the limit probability that a vertex of a connected series-parallel graph In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.  has degree k. then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [B.sup.*] is given by Lemma 4.2 and Equations (8) and (7).

Moreover p(1) = 1, so that the [d.sub.k] are indeed a probability distribution and we have asymptotically, as k [right arrow] [infinity],

[d.sub.k] ~ c x [k.sup.-3/2][q.sup.k],

where c is a positive constant and

q = [((1 + 1/([tau]E([tau], 1)))[e.sup.-1/[tau]E([tau], 1)] - 1).sup.-1] [approximately equal to] 0.7504161.

5 Quadrangulations and 3-connected planar graphs

The goal of this section is to find the generating function of 3-connected planar graphs according to the degree of the root. This is an essential ingredient in the next section.

First we work out the problem for simple quadrangulations, which are in bijection with 3-connected maps. In order to do that we must revisit re·vis·it  
tr.v. re·vis·it·ed, re·vis·it·ing, re·vis·its
To visit again.

n.
A second or repeated visit.



re
 the classical work of Brown and Tutte (6) on 2-connected (non-separable) maps. Finally, using the fact that a 3-connected planar graph has a unique embedding, we finish the job.

5.1 Simple quadrangulations

A rooted quadrangulation is a planar map where every face is a quadrangle quadrangle

Rectangular open space completely or partially enclosed by buildings of an academic or civic character. The grounds of a quadrangle are often grassy or landscaped.
, and with a distinguished directed edge of the external face, which is called the root edge of the quadrangulation. The root vertex of the quadrangulation is the first vertex of the root edge. A diagonal is an internal path of length 2 joining two opposite vertices of the external face. A quadrangulation is simple if it has no diagonal, every cycle of length 4 other than the external one defines a face, and it is not the trivial map reduced to a single quadrangle. In Section 5 of (19) it is shown how to count simple quadrangulations. Here we extend this result to count them also according to the degree of the root vertex.

A quadrangulation is bipartite and connected, so if we fix the colour of the root vertex there is a unique way of 2-colouring the vertices. We call the two colours black and white, and we assume the root is black. Diagonals are called black or white, according to the colour of the external vertices they join.

Let F(x, y, w) be the GF of rooted quadrangulations, where the variables x, y and w mark, respectively, the number of black vertices minus one, the number of white vertices minus one, and the degree of the root vertex minus one. Generating functions for maps are always ordinary, since maps are unlabelled objects.

The generating functions [F.sub.N], [F.sub.B] and [F.sub.W] are associated, respectively, to quadrangulations with no diagonal, to those with at least one black diagonal (at the root vertex), and to those with at least one whit diagonal (not at the root vertex). By planarity
This article is about the game; for the graph theory property, see Planar graph.


Planarity is the name of a puzzle computer game based on a concept by Mary Radcliffe at Western Michigan University[1].
 only one of the two kinds of diagonals can appear in a quadrangulation; it follows that

F(x, y, w) = [F.sub.N](x, y, w) + [F.sub.B](x, y, w) + [F.sub.W](x, y, w).

A quadrangulation with a diagonal can be decomposed de·com·pose  
v. de·com·posed, de·com·pos·ing, de·com·pos·es

v.tr.
1. To separate into components or basic elements.

2. To cause to rot.

v.intr.
1.
 into two quadrangulations, by considering the maps to the left and to the right of this diagonal. This gives raise to the equations

[F.sub.B](x, y, w) = ([F.sub.N](x, y, w) + [F.sub.W](x, y, w))F(x, y, w)/x,

[F.sub.W](x, y, w) = ([F.sub.N](x, y, w) + [F.sub.B](x, y, w))F(x, y, 1)/y.

In the second case, only one of the two quadrangulations contribute to the degree of the root vertex; this is the reason why the term F(x, y, 1) appears. The x and the y in the denominators appear because the three vertices of the diagonal are common to the two quadrangulations. Since we are considering vertices minus one, we only need to correct the colour that appears twice at the diagonal. Incidentally, no term w appears in the equations for the same reason.

Let us write F = F(x, y, w) and F(1) = F(x, y, 1). From the previous equations we deduce de·duce  
tr.v. de·duced, de·duc·ing, de·duc·es
1. To reach (a conclusion) by reasoning.

2. To infer from a general principle; reason deductively:
 that

F = [F.sub.N] + [F.sub.B] + [F.sub.W] = ([F.sub.N] + [F.sub.B])(1 + F/x),

F = [F.sub.N] + [F.sub.B] + [F.sub.W] = ([F.sub.N] + [F.sub.W])(1 + F(1)/y),

so that

F + [F.sub.N] = ([F.sub.N] + [F.sub.B]) + ([F.sub.N] + [F.sub.W]) = F (1/1 + F/x + 1/1 + F(1)/y),

and finally

[F.sub.N] = F (1/1 + F/x + 1/1 + F(1)/y - 1). (10)

Now we proceed to count simple quadrangulations. We use the following combinatorial decomposition decomposition /de·com·po·si·tion/ (de-kom?pah-zish´un) the separation of compound bodies into their constituent principles.

de·com·po·si·tion
n.
1.
 of quadrangulations with no diagonals in terms of simple quadrangulations: all quadrangulations with no diagonals, with the only exception of the trivial one, can be decomposed uniquely into a simple quadrangulation q and as many quadrangulations as internal faces q has (replace every internal face of q by its corresponding quadrangulations)

Let

Q(x, y, w) = [summation over (i,j,k)][q.sub.i,j,k][x.sup.i][y.sup.j][w.sup.k],

be the GF of simple quadrangulations, where x, y and w have the same meaning as for F. [Note: In (19) this GF is called [Q.sup.*.sub.N].] We translate the combinatorial decomposition of simple quadrangulations into generating functions as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

where we are using the fact that a quadrangulation counted by [q.sub.i,j,k] has i + j + 2 vertices, i + j - 1 internal faces, and k of them are incident to the root vertex.

At this point we change variables as X = F(1)/y, Y = F(1)/x and W = F/F F/F Female/Female (fanfic pairing)
F/F Flip-Flop
F/F Frame Format
F/F Factory Fitted
F/F Friends/Favorites
F/F Fleet/Force
(1). Then Equations (10) and (11) can be rewritten as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

The last equation would be an explicit expression of Q in terms of X, Y, W if it were not for the term F(1)w = F(x, y, 1)w. In (19) it is shown that

F(1) = RS/[(1 + R + S).sup.3], (13)

where R = R(X, Y) and S(X, Y) are algebraic functions defined by

R = X[(S + 1).sup.2], S = Y[(R + 1).sup.2]. (14)

Hence it remains only to obtain an expression for w = w(X, Y, W) to obtain an explicit expression for Q. This done in the next subsection subsection
Noun

any of the smaller parts into which a section may be divided

Noun 1. subsection - a section of a section; a part of a part; i.e.
.

5.2 Rooted non-separable planar maps

In (6), the authors studied the generating function h(x, y, w) of rooted non-separable planar maps where x, y and w count, respectively the number of vertices minus one, the number of faces minus one, and the valency valency - degree  (number of edges) of the external face. [Note: In (6) the variable z is used instead of w.] There is a bijection between rooted quadrangulations and non-separable rooted planar maps: black and white vertices in the quadrangulation correspond, respectively, to faces and vertices of the map; quadrangles become edges; and the root vertex becomes the external face, and its degree becomes its valency). As a consequence h(y, x, w) = wF(x, y, w), where the extra factor w appears because in F we are counting the degree of the root vertex minus one. It follows that Equation (3.9) from (6) becomes

(1 - w)(1 - yw)wF = -[w.sup.2][F.sup.2] + (-xw + wF(1))wF + x[w.sup.2](x(1 - w) + F(1))

By dividing both sides by F[(1).sup.2], and rewriting in terms of X = F(1)/y, Y = F(1)/x and W = F/F(1), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

Observe that this is a quadratic equation quadratic equation

Algebraic equation of particular importance in optimization. A more descriptive name is second-degree polynomial equation. Its standard form is ax2 + bx + c
 in w. Solving for w in (15) and using (13) and (14) we get (the plus sign is because [T.sup.*] has positive coefficients in coming Theorem 5.1)

w= -[w.sub.1](R, S, W) + (R - W + 1)[square root of [w.sub.2](R, S, W)]/2[(S + 1).sup.2](SW + [R.sup.2] + 2R + 1), (16)

where [w.sub.1] (R, S, W) and [w.sub.2] (R, S, W) are polynomials given by

[w.sub.1] = -RS[W.sup.2] + W (1 + 4S + 3R[S.sup.2] +5[S.sup.2] + [R.sup.2] + 2R + 2[S.sup.3] + 3[R.sup.2]S + 7RS) + [(R + 1).sup.2](R + 2S + 1 + [S.sup.2]), (17)

[w.sub.2] = [R.sup.2][S.sup.2][W.sup.2] - 2W RS(2[R.sup.2]S + 6RS + 2[S.sup.3] + 3R[S.sup.2] +5[S.sup.2] + [R.sup.2] + 2R + 4S + 1) + [(R + 1).sup.2][(R + 2S + 1 + [S.sup.2]).sup.2]. (18)

The reason we choose to write w as a function of (R, S, W) instead of (X, Y, W) will become clear later on.

Thus, together with Equations (12) and (13), we have finally obtained an explicit expression for the generating function Q (X, Y, W) of simple quadrangulations in terms of W and algebraic functions R (X, Y) and S(X, Y).

5.3 3-connected planar graphs

Let [T.sup.*] (x, z, w) be the GF of 3-connected planar graphs, where one edge is taken as the root and given a direction, and where x counts vertices, z counts edges, and w counts the degree of the tail of the root edge. Now we relate [T.sup.*] to the GF Q (X, Y, W) of simple quadrangulations.

By the bijection between simple quadrangulations and 3-connected planar maps, and using Euler's relation, the GF xwQ(xz, z, w) counts rooted 3-connected planar maps, where z marks edges (we have added an extra term w to correct the 'minus one' in the definition of Q).

By Whitney's theorem 3-connected planar graphs have a unique embedding on the sphere. As noticed in (1), the are two ways of rooting an embedding of a directed edge-rooted graph in order to get a rooted map, since there are two ways of choosing the root face adjacent to the root edge. It follows that

[T.sup.*](x, z, w) = xw/2 Q(xz, z, w). (19)

Theorem 5.1 The generating function of directed edge-rooted 3-connected planar graphs, where x, z, w mark, respectively, vertices, edges, and the degree of the root vertex, is equal to

[T.sup.*] = [x.sup.2][z.sup.2][w.sup.2]/2 (1/1 + wz + 1/1 + xz - 1 - [(u + 1).sup.2] (-[w.sub.1](u, v, w) + (u - w + 1)[square root of [w.sub.2](u, v, w)])/2w(vw + [u.sup.2] + 2u + 1)[(1 + u + v).sup.3]), (20)

where u and v are algebraic functions defined by

u = xz[(1 + v).sup.2], v = z[(1 + u).sup.2], (21)

and [w.sub.1] (u, v, w) and [w.sub.2] (u, v, w) are given by (17) and (18) replacing R, S, W by u, v, w, respectively.

6 Planar graphs

6.1 2-connected planar graphs

Let [B.sup.*] (x, y, w), the generating function of rooted 2-connected planar graphs taking into account the degree of the root. As for series series-parallel graphs we have to work with networks.

Let [T.sup.*] (x, z, w) be the GF for directed edge-rooted 3-connected planar maps as in the previous section. As in Section 4, we denote by D(x, y, w) and S(x, y, w), respectively, the GFs of (planar) networks and series networks, with the same meaning for the variables x, y and w.

Lemma 6.1 We have

D(x, y, w) = (1 + yw) exp (S(x, y, w) + 1/[x.sup.2]D(x, y, w) [T.sup.*] (x, E(x, y), D(x, y, w)/E(x, y))) - 1

S(x, y, w) = xE(x, y) (D(x, y, w) - S(x, y, w)),

where E(x, y) = D(x, y, 1) is the GF for planar networks (without marking the degree of the root).

As in Lemma 4.1, and for the same reason, we have

W [partial derivative][B.sup.*](x, y, w)/[partial derivative]w = xyw exp (S(x, y, w) + 1/[x.sup.2]D(x, y, w) [T.sup.*] (x, E(x, y), D(x, y, w)/E(x, y)))

Lemma 6.2 The generating function of rooted 2-connected planar graphs is equal to

[B.sup.*] (x, y, w) = x (D - xED/(1 + x E(1 + D/2))-1 + D/xD [T.sup.*](x, E, D/E) +1/x [[integral].sup.D.sub.0] [T.sup.*] (x, E, t/E)/t dt, (22)

where for simplicity we let D = D(x, y, w) and E = E(x, y).

In order to get a full expression for [B.sup.*] (x, y, w), it remains to compute the integral in the formula of the previous lemma.

Lemma 6.3 Let [T.sup.*] (x, z, w) be the GF of 3-connected planar graphs as before. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the expressions Q, [Q.sub.1], and [Q.sub.2] are given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Combining Lemmas This following is a list of lemmas (or, "lemmata", i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list of axioms, list of theorems and list of conjectures.  6.2 and 6.3 we can produce an explicit (although quite long) expression for [B.sup.*] (x, y, w) in terms of D(x, y, w), E(x, y), and the algebraic functions u(x, y), v(x, y). This is needed in the next section for computing the singular expansion of [B.sup.*] (x, y, w) at its dominant singularity.

6.2 Singular expansions

In this section we find singular expansions of [T.sup.*] (x, z, w), D(x, y, w) and [B.sup.*] (x, y, w) at their dominant singularities. As we show here, these singularities do not depend on w and were found in (1) and (13).

However the coefficients of the singular expansions do depend on w, and our task is to compute them exactly in each case.

What is needed in the next section is the singular expansion for [B.sup.*], but to compute it we first need the singular expansions of u, v, [T.sup.*] and D (for a and v compare also with (2) and (1)).

Lemma 6.4 Suppose that x and w are sufficiently close to the positive real axis and that [absolute value of w] [less than or equal to] 1. Then the dominant singularity z = [tau](x) of [T.sup.*] (x, z, w) does not depend on w. The singular expansion at [tau](x) is

[T.sup.*] (x, z, w) = [T.sub.0] (x, w) + [T.sub.2] (x, w)[Z.sup.2] + [T.sub.3] (x, w)[Z.sup.3] + O([Z.sup.4]), (23)

where Z = [square root of 1 - z/T(x), and the expressions for the [T.sub.i] are analytic functions of x and w.

Similary we get an alternate expansion in the variable x.

Lemma 6.5 Suppose that z and w are sufficiently close to the positive real axis and that [absolute value of w] [less than or equal to] 1. Then the dominant singularity x = r(z) of [T.sup.*] (x, z, w) does not depend on w. The singular expansion at r(z) is

[T.sup.*] (x, z, w) = [[??].sub.0] (z, w) + [[??].sub.2] (z, w) [X.sup.2] + [[??].sub.3] (x, w)[X.sup.3] + O([X.sup.4]). (24)

Using Lemma 6.1 and the previous result we obtain the following.

Lemma 6.6 Suppose that y and w are sufficiently close to the positive real axis and that [absolute value of w] [less than or equal to] 1. Then the dominant singularity x = R(y) of D(x, y, w) does not depend on w. The singular expansion at R(y) is

D(x, y, w) = [D.sub.0] (y, w) + [D.sub.2] (y, w)[X.sup.2] + [D.sub.3] (Y, w)[X.sup.3] + O([X.sup.4]), (25)

where X = [square root of 1 - x/R(y), and the [D.sub.i] are analytic functions.

And finally from Lemmas 6.2 and 6.3 we obtain the singular expansion for [B.sup.*], which is the essential piece in our analysis.

Lemma 6.7 Suppose that y and w are sufficiently close to the positive real axis and that [absolute value of w] [less than or equal to] 1. Then the dominant singularity x = R(y) of [B.sup.*] (x, y, w) does not depend on w, and is the same as for D (x, y, w). The singular expansion at R(y) is

[B.sup.*] (x, y, w) = [B.sub.0] (y, w) + [B.sub.2] (y, w)[X.sup.2] + [B.sub.3] (Y, w)[X.sup.3] + O([X.sup.4]), (26)

where X = [square root of 1 - x/R(y)], and the [B.sub.i] are analytic functions.

6.3 Degree distribution for planar graphs

The following is the analogous of Lemma 3.1. The difference now is that we are composing two singular expansions and, moreover, they are of type 3/2.

Lemma 6.8 Let f(x) = [[summation].sub.n[greater than or equal to]0] [a.sub.n][x.sup.n]/n! denote the exponential generating function of a sequence [a.sub.n] of non-negative real numbers and suppose that f(x) has exactly one dominating singularity at x = [rho] of the form

f(x) = [f.sub.0] + [f.sub.0] [X.sup.2] + [f.sub.0] [X.sup.3] + [phi]([X.sup.4]),

where X = [square root of 1 - x/[rho], and has an analytic continuation to the region {x [member of] C : [absolute value of x] < [rho] + [epsilon] \ {x [member of] R : x [greater than or equal to] [rho]} for some [epsilon] > 0. Further, let H (x, z, w) denote a function that has a dominant singularity at z = f([rho]) > 0 of the form

H (x, z, w) = [h.sub.0] (x, w) + [h.sub.2] (x, w)[Z.sup.2] + [h.sub.3] (x, w)[Z.sup.3] + O([Z.sup.4]),

where w is considered as a parameter, Z = [square root of 1 - z/f([rho])], the functions [h.sub.j] (x, w) are analytic in x, and H(x, z, w) has an analytic continuation ...

Then the function

[f.sub.H](x) = H (x, f (x), w)

has a power series expansion [f.sub.H](x) = [[summation].sub.n[greater than or equal to]0] [b.sub.n][x.sup.n]/n! and the coefficients [b.sub.n] satisfy

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (27)

Applying the previous lemma with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and f(x) = xC'(x), we obtain:

Theorem 6.9 Let [d.sub.k] be the probability that a vertex of a connected planar graph has degree k. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [B.sub.j] (y, w), j = 0, 2, 3 are the analytic functions given in Lemma 6.7.

Moreover, p(1) = 1, so that the [d.sub.k] are indeed a probability distribution and we have asymptotically, as k [right arrow] [infinity],

[d.sub.k] ~ [ck.sup.-1/2][q.sup.k],

where c is a positive constant and q [approximately equal to] 0.6734506.

References

[1] E. A. Bender, Z. Gao, N. C. Wormald, The number of 2-connected labelled planar graphs, Elec. J. Combinatorics combinatorics (kŏm'bənətôr`ĭks) or combinatorial analysis (kŏm'bĭnətôr`ēəl)  9 (2002), #43.

[2] E.A. Bender, L.B. Richmond, The asymptotic enumeration of rooted convex Convex

Curved, as in the shape of the outside of a circle. Usually referring to the price/required yield relationship for option-free bonds.
 polyhedra, J. Combin. Theory B 3 (1994) 276-283.

[3] N. Bernasconi, K. Panagiotou, A. Steger, On the degree sequences of random and outerplanar and series-parallel graphs (manuscript).

[4] M. Bodirsky, O. Gimenez, M. Kang, and M. Noy, Enumeration and limit laws for series-parallel graphs, Europ. J. Combinatorics 28 (2007), 2091-2105.

[5] N. Bonichon, C. Gavoille, N. Hanusse, D. Poulalhon, G. Schaeffer, Planar Graphs, via Well-Orderly Maps and Trees, Graphs and Combinatorics 22 (2006), 185-202.

[6] W. G. Brown, W. T. Tutte, On the enumeration of rooted non-separable planar maps, Canad. J. Math. 16(1964)572-577.

[7] A. Denise, M. Vasconcellos, D. J. A. Welsh, The random planar graph, Congr. Numer. 113 (1996), 61-79.

[8] M. Drmota, O. Gimenez, M. Noy, The number of vertices of given degree in series-parallel graphs (submitted).

[9] P. Flajolet, A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), 216-240.

[10] P. Flajolet and R. Sedgewick, Analytic combinatorics Analytic combinatorics is a branch of combinatorics that describes combinatorial classes using generating functions, which are often analytic functions, but sometimes formal power series. , to be published in 2008 by Cambridge University Press Cambridge University Press (known colloquially as CUP) is a publisher given a Royal Charter by Henry VIII in 1534, and one of the two privileged presses (the other being Oxford University Press). , preliminary version available at http://algo.inria.fr/flajolet/Publications

[11] Z. Gao, N. C. Wormald, The distribution of the maximum vertex degree in random planar maps. J. Combin. Theory Ser. A 89 (2000), 201-230.

[12] S. Gerke, C. McDiarmid, On the Number of Edges in Random Planar Graphs, Comb. Prob. and Computing 13 (2004), 165-183.

[13] O. Gimenez, M. Noy, The number of planar graphs and properties of random planar graphs, DMTCS DMTCS Discrete Mathematics and Theoretical Computer Science  Proceedings, vol. AD, 2005, pp. 147-156. Full version to appear in J. Amer Math. Soc.

[14] O. Gimenez, M. Noy, J. Rue rue, common name for various members of the family Rutaceae, a large group of plants distributed throughout temperate and tropical regions and most abundant in S Africa and Australia. Most species are woody shrubs or small trees; many are evergreen and bear spines. , Graph classes with given 3-connected components: asymptotic counting and critical phenomena, Proc. of Eurcocomb 2007, Elec. Notes in Discrete Math. 29 (2007), 521-529.

[15] V. A. Liskovets, A pattern of asymptotic vertex valency distributions in planar maps, J. Combin. Theory Ser. B 75 (1999), 116-133.

[16] C. McDiarmid, Random graphs on surfaces, J. Combin. Theory Ser. B. 98 (2008), 778-797.

[17] C. McDiarmid, B. Reed, On the maximum degree of a random planar graph (manuscript).

[18] C. McDiarmid, A. Steger, D. J. A. Welsh, Random planar graphs. J. Combin. Theory Ser. B 93 (2005), 187-205.

[19] R. C, Mullin, P. J. Schellenberg, The enumeration of c-nets via quadrangulations, J. Combin. Theory 4 (1968), 259-276.

[20] M. Noy, Random planar graphs and the number of planar graphs in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh (2007), pp. 213-233.

[21] D. Osthus, H. J. PrOmel, A. Taraz, On random planar graphs, the number of planar graphs and their triangulations, J. Combin. Theory Ser. B 88 (2003), 119-134.

[22] T. R. S. Walsh, Counting labelled three-connected and homeomorphically irreducible irreducible /ir·re·duc·i·ble/ (ir?i-doo´si-b'l) not susceptible to reduction, as a fracture, hernia, or chemical substance.

ir·re·duc·i·ble
adj.
1.
 two-connected graphs, J. Combin. Theory Ser. B 32 (1982), 1-11.

Michael Drmota (1) and Omer Gimenez (2) and Marc Noy (2,[dagger])

(1) Tecnische Universitat Wien, Wiedner Haupstrasse 8-10, A-1040 Wien, Austria.

(2) Universitat Politecnica de Catalunya, Jordi Girona 1-3, 08034 Barcelona, Spain.

([dagger]) Research supported in part by Project MTM MTM Medication Therapy Management
MTM Minutes to Midnight (Linkin Park album)
MTM Mary Tyler Moore (actress)
MTM Made to Measure
MTM Motoren-Technik-Mayer
MTM Methods Time Measurement
2005-08618C02-01.
Tab. 1: Degree distribution for small degrees.

                    [d.sub.1]    [d.sub.2]    [d.sub.3]

Outerplanar         0.1365937    0.2875331    0.2428739
Series-Parallel     0.1102133    0.3563715    0.2233570
Planar              0.0367284    0.1625794    0.2354360

                    [d.sub.4]    [d.sub.5]    [d.sub.6]

Outerplanar         0.1550795    0.0874382    0.0460030
Series-Parallel     0.1257639    0.0717254    0.0421514
Planar              0.1867737    0.1295023    0.0861805

Tab. 2: Asymptotic estimates of [d.sub.k] for large k. The constants c
and q in each case are defined analytically.

Outerplanar        c x [k.sup.1/4][e.sup.[square root of k]][q.sup.k]
Series-Parallel    c x [k.sup.-3/2][q.sup.k]
Planar             c x [k.sup.-1/2][q.sup.k]

Outerplanar        q [approximately equal to] 0.3808138
Series-Parallel    q [approximately equal to] 0.7504161
Planar             q [approximately equal to] 0.6734506
COPYRIGHT 2008 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

 Reader Opinion

Title:

Comment:



 

Article Details
Printer friendly Cite/link Email Feedback
Author:Drmota, Michael; Gimenez, Omer; Noy, Marc
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUAU
Date:Jan 1, 2008
Words:7164
Previous Article:The degree distribution of thickened trees.
Next Article:Constructions for clumps statistics.
Topics:

Terms of use | Copyright © 2014 Farlex, Inc. | Feedback | For webmasters