Type-II Apollonian network: More robust and more efficient Apollonian network

The family of planar graphs is a particularly important family and models many networks including the layout of printed circuits. The widely-known Apollonian packing process has been used as guideline to create the typical Apollonian network with planarity. In this paper, we propose a new principled framework based on the Apollonian packing process to generate model as complex network, and obtain a family of new networks called Type-II Apollonian network A_t. While our network and the typical Apollonian network are maximal planar, the former turns out to be Hamiltonian and Eulerian, however, the latter is not. Then, we in-depth study some fundamental structural properties on network A_t, and verify that network A_t is sparse, has scale-free feature and small-world property, and exhibits disassortative mixing structure. Next, we derive the asymptotic solution of the spanning tree entropy of network A_t by designing an effective algorithm, which suggests that Type-II Apollonian network is more robust to a random removal of edges than the typical Apollonian network. Additionally, we study trapping problem on network A_t, and use average trapping time as metric to show that Type-II Apollonian network A_t has more efficient underlying structure for fast information diffusion than the typical Apollonian network.