Improved enumeration of simple topological graphs

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Improved enumeration of simple top ologial graphs ∗ Jan Kyn£l † 1 1 Department of Applied Mathematis and Institute for Theoretial Computer Siene, Charles University, Faulty of Mathematis and Physis, Malostranské nám. 25, 118 00 Praha 1, Czeh Republi Abstrat A simple topologial graph T= (V(T), E(T)) is a drawing of a graph in the plane where every two edges have at most one ommon p oint (an endp oint or a rossing) and no three edges pass through a single rossing. Top ologial graphs G and H are isomorphi if H an be obtained from G by a homeomorphism of the sphere, and weakly isomorphi if G and H have the same set of pairs of rossing edges. We generalize results of Pah and Tóth and the author's previous results on ounting dierent drawings of a graph under both notions of isomorphism. We prove that for every graph G with n verties, m edges and no isolated verties the numb er of weak isomorphism lasses of simple topologial graphs that realize G is at most 2O(n2log(m/n)) , and at most 2O(mn1/2log n) if m≤n3/2 . As a onsequene we obtain a new upp er b ound 2O(n3/2log n) on the numb er of intersetion graphs of n pseudosegments. We improve the upp er b ound on the numb er of weak isomorphism lasses of simple omplete top ologial graphs with n verties to 2n2·α(n)O(1) , using an upp er b ound on the size of a set of p ermutations with b ounded VC-dimension reently proved by Cibulka and the author. We show that the numb er of isomorphism lasses of simple top ologial graphs that realize G is at most 2m2+O(mn) and at least 2Ω(m2) for graphs with m > (6 + ε)n . 1 Intro dution and the results A topologial graph T= (V(T), E(T)) is a drawing of a graph G in the plane with the following prop erties. The verties of G are represented by a set V(T) of distint p oints in the plane and the edges of G are represented by a set E(T) of simple urves onneting the orresp onding pairs of p oints. We all the elements of ∗ The full version of the pap er is available [8℄. † Email: kynlkam.m.uni.z. The author was supp orted by the GraDR EUROGIGA GACR pro jet No. GIG/11/E023 and by the grant SVV-2013-267313 (Disrete Mo dels and Algorithms). Part of the researh was onduted during the Sp eial Semester on Disrete and Computational Geometry at Éole Polytehnique Féderale de Lausanne, organized and supp orted by the CIB (Centre Interfaultaire Bernoulli) and the SNSF (Swiss National Siene Foundation). V(T) and E(T) the verties and the edges of T . The drawing has to satisfy the following general p osition onditions: (1) the edges pass through no verties ex- ept their endp oints, (2) every two edges have only a nite numb er of intersetion points, (3) every interse- tion p oint of two edges is either a ommon endp oint or a proper rossing (touhing of the edges is not allowed), and (4) no three edges pass through the same rossing. A top ologial graph is simple if every two edges have at most one ommon point, whih is either a ommon endp oint or a rossing. A top ologial graph is omplete if it is a drawing of a omplete graph. We use two dierent notions of isomorphism to enumerate top ologial graphs. Top ologial graphs G and H are weakly isomorphi if there exists an inidene preserving one-to-one orresp ondene b etween V(G), E(G) and V(H), E(H) suh that two edges of G ross if and only if the orresp onding two edges of H do. Note that every topologial graph G drawn in the plane indues a drawing GS2 on the sphere, whih is obtained by a standard one-p oint ompatiation of the plane. Top ologial graphs G and H are isomorphi if there exists a homeomorphism of the sphere whih transforms GS2 into HS2 . The isomorphism an b e also dened in a ombinatorial way. Unlike the isomorphism, the weak isomorphism an hange the faes of the involved top ologial graphs, the order of rossings along the edges and also the yli orders of edges around verties. For ounting the (weak) isomorphism lasses, we onsider all the graphs lab eled. That is, eah vertex is assigned a unique label from the set {1,2,...,n} , and we require the (weak) isomorphism to preserve the lab els. Mostly it makes no signiant dierene in the results as we op erate with quantities asymptotially larger than n! . For a graph G , let Tw(G) b e the number of weak isomorphism lasses of simple top ologial graphs that realize G . Pah and Tóth [13℄ and the author [6℄ proved the following lower and upp er b ounds on Tw(Kn) . Theorem 1 [6, 13℄ For the number of weak isomorphism lasses of simple drawings of Kn , we have 2Ω(n2)≤Tw(Kn)≤((n−2)!)n= 2O(n2log n). 99 Improved enumeration of simple top ologial graphs We prove generalized upp er and lower b ounds on Tw(G) for all graphs G . Theorem 2 Let G be a graph with n verties and m edges. Then Tw(G)≤2O(n2log(m/n)). If m < n3/2 , then Tw(G)≤2O(mn1/2log n). Let ε > 0 . If G is a graph with no isolated verties and at least one of the onditions m > (1 + ε)n or ∆(G)<(1 −ε)n is satised, then Tw(G)≥2Ω(max(m,n log n)). We also improve the upp er b ound from Theorem 1. Theorem 3 We have Tw(Kn)≤2n2·α(n)O(1) . Here α(n) is the inverse of the Akermann funtion. It is an extremely slowly growing funtion, whih an b e dened in the following way [10℄. α(m) := min{k: αk(m)≤3} where αd(m) is the d th funtion in the inverse Akermann hierarhy . That is, α1(m) = ⌈m/2⌉ , αd(1) = 0 for d≥2 and αd(m) = 1+αd(αd−1(m)) for m, d ≥2 . The onstant in the O(1) notation in the exp onent is huge (roughly 4304 ), due to a Ramsey-type argument used in the pro of. In the pro of of Theorem 3 we use the fat that for simple omplete top ologial graphs, the weak isomorphism lass is determined by the rotation system [7, 13℄. This is ombined with a Ramsey-typ e theorem by Pah, Solymosi and Tóth [12℄, whih says that a simple omplete top ologial graph with su- iently many verties ontains a subgraph weakly isomorphi to a onvex graph or a twisted graph of given size; see Figure 1. One we have a onvex graph with 5 verties or a twisted graph with 6 verties, we may restrit the set of p ossible rotations of other verties in terms of forbidden subp ermutations. The last main ingredient is a reent ombinatorial result, a slightly sup erexp onential upp er b ound on the size of a set of p ermutations with bounded VC-dimension obtained together with Josef Cibulka [4℄. The metho d in the pro of of Theorem 2 is more topologial, gives a slightly weaker upp er b ound, but an b e generalized to all graphs. Here the main to ol is a onstrution of a topologial spanning tree T of G , whih is a simply onneted subset of the single topologial omp onent of G ontaining all verties of G and satisfying the property that the only nonseparating p oints of T are the verties of G . We nd suh a tree onsisting of O(n) onneted p ortions of edges C5 v1v2v3v4v5v6 T6 Figure 1: The onvex graph C5 and the twisted graph T6 . v1 v2 v4 v3 v5 v6 c1 c2 T v1 c1 1 v2 c2 1 v1 3v1 4c1 2 v5 c3 2 v2 4 v2 3 c3 1 c2 2 v6 Figure 2: A top ologial spanning tree T of a simple top ologial graph with two omp onents (left) and the orresp onding T -representation (right). of G . By utting the plane along T , we obtain the T -representation of G , whih is equivalent to a dis with at most 2mn hords, eah hord orresponding to a portion of some edge of G . See Figure 2. We give an upper bound on the numb er of inequivalent T -representations, exploiting the fat that many portions of edges do not ross. We further generalize Theorem 3 by removing almost all top ologial asp ets of the pro of. The resulting theorem is a purely ombinatorial statement, involving n -tuples of yli p ermutations avoiding a ertain simple substruture. We also onsider the lass of simple omplete top ologial graphs with maximum numb er of rossings and suggest an alternative method for obtaining an upp er b ound on the numb er of weak isomorphism lasses of suh drawings. An arrangement of pseudosegments (or also 1 - strings ) is a set of simple urves in the plane suh that any two of the urves ross at most one. An intersetion graph of pseudosegments (also alled a string graph of rank 1 ) is a graph G suh that there exists an arrangement of pseudosegments with one pseudosegment for eah vertex of G and a pair of pseudosegments rossing if and only if the orresponding pair of verties forms an edge in G . Using tools from extremal graph theory, Pah and Tóth [13℄ proved that the numb er of intersetion graphs of n pseudosegments is 2o(n2) . As a sp eial ase of Theorem 2 we 100 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 obtain the following upper b ound. Theorem 4 There are at most 2O(n3/2log n) interse- tion graphs of n pseudosegments. The b est known lower b ound for the numb er of (unlab eled) intersetion graphs of n pseudosegments is 2Ω(nlog n) . This follows by a simple onstrution or from the the fat that there are 2Θ(nlog n) nonisomorphi p ermutation graphs with n verties. Let T(G) b e the numb er of isomorphism lasses of simple top ologial graphs that realize G . The following theorem generalizes the result T(Kn) = 2Θ(n4) from [7℄. Theorem 5 Let G be a graph with n verties, m edges and no isolated verties. Then T(G)≤ 2m2+O(mn) . More preisely, T(G)≤6mn 2mnm2+ 6mn m2 2+ 2mn·2O(nlog n) ≤2m2+2mn(1+3 log23)+O(nlog n), and T(G)≤2m2+4mn ·2mn +m2 2 2mn ·2O(nlog n) ≤2m2+2mn(log(1+ m 4n)+2+log2e)+O(nlog n). Let ε > 0 . For graphs G with m > (6 + ε)n we have T(G)≥2Ω(m2). For graphs G with m > ω(n) we have T(G)≥2m2/60 −o(1). The two upper b ounds on T(G) ome from two essentially dierent approahes to enumerating isomorphism lasses of T -representations. In the rst approah, we redue the problem to enumerating simple quadrangulations of the dis [9℄. In the seond approah, we split the problem into two parts: enumerating hord diagrams [14℄ and enumerating isomorphism lasses of arrangements of pseudohords . The rst metho d gives better asymptoti results for dense graphs, whereas the seond one is b etter for sparse graphs (roughly, with at most 35n edges). For graphs with m=O(n) the seond term in the exp onent b eomes more signiant. Sine m≥n/2 , the exp onent in the rst upp er b ound an be b ounded by 23.118m2+o(1), using the entropy b ound for the binomial oeient. Similarly, the exp onent in the se- ond upp er b ound an b e b ounded by 11.265m2+o(1). For suh very sparse graphs (for example, mathings), however, b etter upp er b ounds an b e dedued more diretly from other known results. The upp er b ound T(G)≤2O(m2) is trivially obtained from the upper b ound on the number of unlab eled plane graphs (or planar maps). Indeed, every drawing G of G an b e transformed into a plane graph H by subdividing the edges of G by its rossings and regarding the rossings of G as new 4 -valent verties in H . The graph H has thus at most n+m 2 verties, at most m+ 2m 2=m2 edges, no lo ops and no multiple edges. Tutte [17℄ showed that there are 2(2M)!3M M!(M+ 2)! = 2(log2(12)+o(1))M ro oted onneted planar maps with M edges (see also [2, 3, 5℄). Walsh and Lehman [18℄ showed that the numb er of ro oted onneted planar lo opless maps with M edges is 6(4M+ 1)! M!(3M+ 3)! = 2(log2(256/27)+o(1))M. This implies the upper b ound T(G)≤ 2(log2(256/27)+o(1))m2 . Somewhat b etter estimates ould be obtained by reduing the problem to ounting 4 -regular planar maps [15, 16℄, sine typially almost all verties in H are the 4 -valent verties obtained from the rossings of G . But suh a redution would be less straightforward and the resulting upp er b ound 2(1 2log2(196/27)+o(1))m2 still relatively high for dense graphs (for graphs with more than 27n edges the two upp er b ounds from Theorem 5 are better). The pro of in [7℄ implies the upp er b ound T(Kn)≤ 2(1/12+o(1))(n4) , although it is not expliitly stated there. However, the key Proposition 7 in [7℄ is in- orret. We prove a orret version in the full paper. Note that by the redution to ounting planar maps, for every xed onstant k , we also obtain the upp er b ound 2O(km2) on the numb er of isomorphism lasses of onneted top ologial graphs with m edges where all pairs of edges are allowed to ross k times. 2 A few op en problems The problem of ounting the asymptoti numb er of nonequivalent simple drawings of a graph in the plane is answered only partially. Many open questions remain. The gap between the lower and upper b ounds on Tw(G) proved in Theorem 2 is wide op en, esp eially for graphs with low density. For graphs with cn2 edges, the lower and upp er b ounds on log Tw(G) differ by a logarithmi fator. We onjeture that the orret answer is loser to the lower b ound. We do not even know whether Tw(G) is a monotone funtion with resp et to the subgraph relation, sine there are simple top ologial graphs that annot b e extended to simple omplete top ologial graphs. Due to somewhat rigid properties of simple omplete top ologial graphs, we have a muh better upper bound for the omplete graph than, say, for the omplete bipartite graph on the same numb er of verties. 101 Improved enumeration of simple top ologial graphs Problem 1 Does the omplete graph Kn maximize the value Tw(G) among the graphs G with n verties? More general ly, is it true that Tw(H)≤Tw(G) if H⊆ G ? Our metho ds for proving upp er b ounds on the numb er of weak isomorphism lasses of simple top ologial graphs do not generalize to the ase of top ologial graphs with two rossings p er pair of edges allowed. Problem 2 What is the number of weak isomorphism lasses of drawings of a graph G where every two independent edges are al lowed to ross at most twie and every two adjaent edges at most one? For the omplete graph with n verties, Pah and Tóth [13℄ proved the lower b ound 2Ω(n2log n) and the upp er b ound 2o(n4) . A nontrivial lower bound an b e proved also in the ase when G is a mathing. Akerman et al. [1℄ onstruted a system of n x -monotone urves where every pair of urves interset in at most one p oint where they either ross or touh, with Ω(n4/3) pairs of touhing urves. Eyal Akerman (personal ommuniation) noted that this also follows from an earlier result by Pah and Sharir [11℄, who onstruted an arrangement of n segments with Ω(n4/3) vertially visible pairs of disjoint segments. By hanging the drawing in the neighborho o d of every touhing p oint, we obtain 2Ω(n4/3) dierent intersetion graphs of 2 -interseting urves, also alled string graphs of rank 2 [13℄. This improves the trivial lower bound observed by Pah and Tóth [13℄. Aknowledgements The author thanks Josef Cibulka for disussions ab out enumerating various ombinatorial ob jets. Referenes [1℄ E. Akerman, R. Pinhasi and S. Zerbib, On touhing urves, Bernoul li Reunion Confer- ene on Disrete and Computational Geometry , EPFL, Lausanne, 2012. [2℄ E. A. Bender and L. B. Rihmond, A survey of the asymptoti b ehaviour of maps, Journal of Combinatorial Theory, Series B 40 (3) (1986), 297329. [3℄ E. A. Bender and N. C. Wormald, The numb er of lo opless planar maps, Disrete Mathematis 54 (2) (1985), 235237. [4℄ J. Cibulka and J. Kyn£l, Tight bounds on the maximum size of a set of p ermutations with b ounded VC-dimension, Journal of Combinatorial Theory, Series A 119 (7) (2012), 14611478. [5℄ M. Drmota and M. Noy, Universal exponents and tail estimates in the enumeration of planar maps, Eletroni Notes in Disrete Mathematis 38 (2011), 309317. [6℄ J. Kyn£l, Crossings in top ologial graphs, master thesis, Charles University, Prague, 2006. [7℄ J. Kyn£l, Enumeration of simple omplete top ologial graphs, European Journal of Combinatoris 30 (7) (2009), 16761685. [8℄ J. Kyn£l, Improved enumeration of simple top ologial graphs, submitted. Manusript available at arXiv:1212.2950. [9℄ R.C. Mullin and P.J. Shellenb erg, The enumeration of -nets via quadrangulations, Journal of Combinatorial Theory 4 (3) (1968), 259276. [10℄ G. Nivash, Improved bounds and new tehniques for Davenp ortShinzel sequenes and their generalizations, Journal of the ACM 57 (3) (2010), 144. [11℄ J. Pah and M. Sharir, On vertial visibility in arrangements of segments and the queue size in the Bentley-Ottmann line sweeping algorithm, SIAM Journal on Computing 20 (3) (1991), 460470. [12℄ J. Pah, J. Solymosi and G. Tóth, Unavoidable ongurations in omplete top ologial graphs, Disrete and Computational Geometry 30 (2003), 311320. [13℄ J. Pah and G. Tóth, How many ways an one draw a graph?, Combinatoria 26 (5) (2006), 559576. [14℄ R. C. Read, The hord intersetion problem, Annals of the New York Aademy of Sienes 319 (1) (1979), 444454. [15℄ H. Ren and Y. Liu, Enumerating near-4-regular maps on the sphere and the torus, Disrete Applied Mathematis 110 (23) (2001), 273288. [16℄ H. Ren, Y. Liu and Z. Li, Enumeration of 2-onneted Loopless 4-regular maps on the plane, European Journal of Combinatoris 23 (1) (2002), 93111. [17℄ W. T. Tutte, A ensus of planar maps, Canadian Journal of Mathematis 15 (1963), 249271. [18℄ T. R. S. Walsh and A. B. Lehman, Counting ro oted maps by genus I I I: Nonseparable maps, Journal of Combinatorial Theory, Series B 18 (1975), 222259. 102