In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.
Definition An Apollonian network may be formed, starting from a single triangle embedded in the Euclidean plane, by repeatedly selecting a triangular face of the embedding, adding a new vertex inside the face, and connecting the new vertex to each vertex of the face containing it. In this way, the triangle containing the new vertex is subdivided into three smaller triangles, which may in turn be subdivided in the same way.
Examples The complete graphs on three and four vertices, and , are both Apollonian networks. is formed by starting with a triangle and not performing any subdivisions, while is formed by making a single subdivision before stopping.
The Goldner–Harary graph is an Apollonian network that forms the smallest non-Hamiltonian maximal planar graph.This graph is named after the work of ; however, it appears earlier in the literature, for instance in , p. 357. Another more complicated Apollonian network was used by to provide an example of a 1-tough non-Hamiltonian maximal planar graph.
Graph-theoretic characterizations As well as being defined by recursive subdivision of triangles, the Apollonian networks have several other equivalent mathematical characterizations. They are the chordal maximal planar graphs, the chordal polyhedral graphs, and the planar 3-trees. They are the uniquely 4-colorable planar graphs, and the planar graphs with a unique Schnyder wood decomposition into three trees. They are the maximal planar graphs with treewidth three, a class of graphs that can be characterized by their forbidden minors or by their reducibility under Y-Δ transforms. They are the maximal planar graphs with degeneracy three. They are also the planar graphs on a given number of vertices that have the largest possible number of triangles, the largest possible number of tetrahedral subgraphs, the largest possible number of cliques, and the largest possible number of pieces after decomposing by separating triangles.
Chordality Apollonian networks are examples of maximal planar graphs, graphs to which no additional edges can be added without destroying planarity, or equivalently graphs that can be drawn in the plane so that every face (including the outer face) is a triangle. They are also chordal graphs, graphs in which every cycle of four or more vertices has a diagonal edge connecting two non-consecutive cycle vertices, and the order in which vertices are added in the subdivision process that forms an Apollonian network is an elimination ordering as a chordal graph. This forms an alternative characterization of the Apollonian networks: they are exactly the chordal maximal planar graphs or equivalently the chordal polyhedral graphs.The equivalence of planar 3-trees and chordal maximal planar graphs was stated without proof by . For a proof, see . For a more general characterization of chordal planar graphs, and an efficient recognition algorithm for these graphs, see . The observation that every chordal polyhedral graph is maximal planar was stated explicitly by .
In an Apollonian network, every maximal clique is a complete graph on four vertices, formed by choosing any vertex and its three earlier neighbors. Every minimal clique separator (a clique that partitions the graph into two disconnected subgraphs) is one of the subdivided triangles. A chordal graph in which all maximal cliques and all minimal clique separators have the same size is a -tree, and Apollonian networks are examples of 3-trees. Not every 3-tree is planar, but the planar 3-trees are exactly the Apollonian networks.
Unique colorability Every Apollonian network is also a uniquely 4-colorable graph. Because it is a planar graph, the four color theorem implies that it has a graph coloring with only four colors, but once the three colors of the initial triangle are selected, there is only one possible choice for the color of each successive vertex, so up to permutation of the set of colors it has exactly one 4-coloring. It is more difficult to prove, but also true, that every uniquely 4-colorable planar graph is an Apollonian network. Therefore, Apollonian networks may also be characterized as the uniquely 4-colorable planar graphs. Apollonian networks also provide examples of planar graphs having as few -colorings as possible for .The fact that Apollonian networks minimize the number of colorings with more than four of colors was shown in a dual form for colorings of maps by .
The Apollonian networks are also exactly the maximal planar graphs that (once an exterior face is fixed) have a unique Schnyder wood, a partition of the edges of the graph into three interleaved trees rooted at the three vertices of the exterior face.; .
Treewidth The Apollonian networks do not form a family of graphs that is closed under the operation of taking graph minors, as removing edges but not vertices from an Apollonian network produces a graph that is not an Apollonian network. However, the planar partial 3-trees, subgraphs of Apollonian networks, are minor-closed. Therefore, according to the Robertson–Seymour theorem, they can be characterized by a finite number of forbidden minors. The minimal forbidden minors for the planar partial 3-trees are the four minimal graphs among the forbidden minors for the planar graphs and the partial 3-trees: the complete graph , the complete bipartite graph , the graph of the octahedron, and the graph of the pentagonal prism. The Apollonian graphs are the maximal graphs that do not have any of these four graphs as a minor.The two forbidden minors for planar graphs are given by Wagner's theorem. For the forbidden minors for partial 3-trees (which include also the nonplanar Wagner graph) see and . For direct proofs that the octahedral graph and the pentagonal-prism graph are the only two planar forbidden minors, see and .
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. The dual graphs of the planar partial 3-trees form another minor-closed graph family and are exactly 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. introduced the Δ-Y reducible planar graphs and characterized them in terms of forbidden homeomorphic subgraphs. The duality between the Δ-Y and Y-Δ reducible graphs, the forbidden minor characterizations of both classes, and the connection to planar partial 3-trees are all from .
Degeneracy In every subgraph of an Apollonian network, the most recently added vertex has degree at most three, so Apollonian networks have degeneracy three. The order in which the vertices are added to create the network is therefore a degeneracy ordering, and the Apollonian networks coincide with the 3-degenerate maximal planar graphs.
Extremality Another characterization of the Apollonian networks involves their connectivity. Any maximal planar graph may be decomposed into 4-vertex-connected maximal planar subgraphs by splitting it along its separating triangles (triangles that are not faces of the graph): given any non-facial triangle: one can form two smaller maximal planar graphs, one consisting of the part inside the triangle and the other consisting of the part outside the triangle. The maximal planar graphs without separating triangles that may be formed by repeated splits of this type are sometimes called blocks, although that name has also been used for the biconnected components of a graph that is not itself biconnected. An Apollonian network is a maximal planar graph in which all of the blocks are isomorphic to the complete graph .
In extremal graph theory, Apollonian networks are also exactly the -vertex planar graphs in which the number of blocks achieves its maximum, , and the planar graphs in which the number of triangles achieves its maximum, . Since each subgraph of a planar graph must be a block, these are also the planar graphs in which the number of subgraphs achieves its maximum, , and the graphs in which the number of cliques of any type achieves its maximum, .For the characterization in terms of the maximum number of triangles in a planar graph, see . quote this result and provide the characterizations in terms of the isomorphism classes of blocks and numbers of blocks. The bound on the total number of cliques follows easily from the bounds on triangles and K4 subgraphs, and is also stated explicitly by , who provides an Apollonian network as an example showing that this bound is tight. For generalizations of these bounds to nonplanar surfaces, see .
Geometric realizations
Construction from circle packings
Apollonian networks are named after Apollonius of Perga, who studied the Problem of Apollonius of constructing a circle tangent to three other circles. One method of constructing Apollonian networks is to start with three mutually-tangent circles and then repeatedly inscribe another circle within the gap formed by three previously-drawn circles. The fractal collection of circles produced in this way is called an Apollonian gasket.
If the process of producing an Apollonian gasket is stopped early, with only a finite set of circles, then the graph that has one vertex for each circle and one edge for each pair of tangent circles is an Apollonian network.. The existence of a set of tangent circles whose tangencies represent a given Apollonian network forms a simple instance of the Koebe–Andreev–Thurston circle-packing theorem, which states that any planar graph can be represented by tangent circles in the same way..
Polyhedra
Apollonian networks are planar 3-connected graphs and therefore, by Steinitz's theorem, can always be represented as the graphs of convex polyhedra. The convex polyhedron representing an Apollonian network is a 3-dimensional stacked polytope. Such a polytope can be obtained from a tetrahedron by repeatedly gluing additional tetrahedra one at a time onto its triangular faces. Therefore, Apollonian networks may also be defined as the graphs of stacked 3d polytopes.See, e.g., . 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..
Triangle meshes The recursive subdivision of triangles into three smaller triangles was investigated as an image segmentation technique in computer vision by ; in this context, they called it the ternary scalene triangle decomposition. They observed that, by placing each new vertex at the centroid of its enclosing triangle, the triangulation could be chosen in such a way that all triangles have equal areas, although they do not all have the same shape. More generally, Apollonian networks may be drawn in the plane with any prescribed area in each face; if the areas are rational numbers, so are all of the vertex coordinates..