On the Longest Paths and the Diameter in Random Apollonian Networks

2013/03/21 by Ehsan Ebrahimzadeh, Ebrahimzadeh, Ehsan, Linda Farczadi +11 · 2 citations
Computer Science · Mathematics · #Data Management and Algorithms #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1303.5213

Abstract

We consider the following iterative construction of a random planar triangulation. Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. After n-3 steps, we obtain a random triangulated plane graph with n vertices, which is called a Random Apollonian Network (RAN). We show that asymptotically almost surely (a.a.s.) every path in a RAN has length o(n), refuting a conjecture of Frieze and Tsourakakis. We also show that a RAN always has a path of length (2n-5)^{log 2/log 3}, and that the expected length of its longest path is Omega(n⁰.88). Finally, we prove that a.a.s. the diameter of a RAN is asymptotic to c log n, where c ≈ 1.668 is the solution of an explicit equation.

Cited by

• Scalable Betweenness Centrality Maximization via Sampling
• Toughness and Hamiltonicity in Random Apollonian Networks

Related

• Long paths in random Apollonian networks
• Distances in random Apollonian network structures
• Parallel Random Apollonian Networks
• Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees
• High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks