Apollonian network
[2] In an Apollonian network, every maximal clique is a complete graph on four vertices, formed by choosing any vertex and its three earlier neighbors.
[6] A Y-Δ transform, an operation that replaces a degree-three vertex in a graph by a triangle connecting its neighbors, is sufficient (together with the removal of parallel edges) to reduce any Apollonian network to a single triangle, and more generally the planar graphs that can be reduced to a single edge by Y-Δ transforms, removal of parallel edges, removal of degree-one vertices, and compression of degree-two vertices are exactly the planar partial 3-trees.
Such a polytope can be obtained from a tetrahedron by repeatedly gluing additional tetrahedra one at a time onto its triangular faces.
[11] It is possible to find a representation of any Apollonian network as convex 3d polyhedron in which all of the coordinates are integers of polynomial size, better than what is known for other planar graphs.
[13] It is also possible to carry out the process of subdividing a triangle to form an Apollonian network in such a way that, at every step, the edge lengths are rational numbers; it is an open problem whether every planar graph has a drawing with this property.
[15] Plummer (1992) used Apollonian networks to construct an infinite family of maximal planar graphs with an even number of vertices but with no perfect matching.
In the first stage, starting from a triangle abc, one repeatedly subdivides the triangular face of the subdivision that contains edge bc: the result is a graph consisting of a path from a to the final subdivision vertex together with an edge from each path vertex to each of b and c. In the second stage, each of the triangular faces of the resulting planar graph is subdivided one more time.
[16] László Lovász and Michael D. Plummer conjectured that a similar exponential lower bound holds more generally for every 3-regular graph without cut edges, a result that was later proven.
Andrade et al. (2005) studied power laws in the degree sequences of a special case of networks of this type, formed by subdividing all triangles the same number of times.
[18] Alan M. Frieze and Charalampos E. Tsourakakis analyzed the highest degrees and the eigenvalues of random Apollonian networks.
Takeo (1960) claimed erroneously that all Apollonian networks have Hamiltonian cycles; however, the Goldner–Harary graph provides a counterexample.
If an Apollonian network has toughness greater than one (meaning that removing any set of vertices from the graph leaves a smaller number of connected components than the number of removed vertices) then it necessarily has a Hamiltonian cycle, but there exist non-Hamiltonian Apollonian networks whose toughness is equal to one.
[21] The combinatorial enumeration problem of counting Apollonian triangulations was studied by Takeo (1960), who showed that they have the simple generating function f(x) described by the equation f(x) = 1 + x(f(x))3.
In this generating function, the term of degree n counts the number of Apollonian networks with a fixed outer triangle and n + 3 vertices.
Geometric structures closely related to Apollonian networks have been studied in polyhedral combinatorics since at least the early 1960s, when they were used by Grünbaum (1963) to describe graphs that can be realized as the graph of a polytope in only one way, without dimensional or combinatorial ambiguities, and by Moon & Moser (1963) to find simplicial polytopes with no long paths.
Planar 3-trees, as a class of graphs, were explicitly considered by Hakimi & Schmeichel (1979), Alon & Caro (1984), Patil (1986), and many authors since them.
[22] Other authors applied the same name more broadly to planar 3-trees in their work generalizing the model of Andrade et al. to random Apollonian networks.
