Apollonian network

Last updated
An Apollonian network Apollonian-network.svg
An Apollonian network
The Goldner-Harary graph, a non-Hamiltonian Apollonian network Goldner-Harary graph.svg
The Goldner–Harary graph, a non-Hamiltonian Apollonian network

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.

Contents

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, K3 and K4, are both Apollonian networks. K3 is formed by starting with a triangle and not performing any subdivisions, while K4 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. [1] Another more complicated Apollonian network was used by Nishizeki (1980) 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. [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. 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 k-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. [3] Apollonian networks also provide examples of planar graphs having as few k-colorings as possible for k > 4. [4]

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. [5]

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 K5, the complete bipartite graph K3,3, 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. [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. 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. [7]

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 K4.

In extremal graph theory, Apollonian networks are also exactly the n-vertex planar graphs in which the number of blocks achieves its maximum, n− 3, and the planar graphs in which the number of triangles achieves its maximum, 3n− 8. Since each K4 subgraph of a planar graph must be a block, these are also the planar graphs in which the number of K4 subgraphs achieves its maximum, n− 3, and the graphs in which the number of cliques of any type achieves its maximum, 8n− 16. [8]

Geometric realizations

Construction from circle packings

An example of an Apollonian gasket Apollonian gasket.svg
An example of an Apollonian gasket
Construction of an Apollonian network from a circle packing Circle packing theorem K5 minus edge example.svg
Construction of an Apollonian network from a circle packing

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. [9] 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. [10]

Polyhedra

The triakis tetrahedron, a polyhedral realization of an 8-vertex Apollonian network Triakistetrahedron.jpg
The triakis tetrahedron, a polyhedral realization of an 8-vertex Apollonian network

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. [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. [12]

Triangle meshes

The recursive subdivision of triangles into three smaller triangles was investigated as an image segmentation technique in computer vision by Elcock, Gargantini & Walsh (1987); 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. [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. [14] It is possible in polynomial time to find a drawing of a planar 3-tree with integer coordinates minimizing the area of the bounding box of the drawing, and to test whether a given planar 3-tree may be drawn with its vertices on a given set of points. [15]

Properties and applications

Matching-free graphs

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. Plummer's graphs are formed in two stages. 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. If the path from a to the final subdivision vertex of the first stage has even length, then the number of vertices in the overall graph is also even. However, approximately 2/3 of the vertices are the ones inserted in the second stage; these form an independent set, and cannot be matched to each other, nor are there enough vertices outside the independent set to find matches for all of them.

Although Apollonian networks themselves may not have perfect matchings, the planar dual graphs of Apollonian networks are 3-regular graphs with no cut edges, so by a theorem of Petersen (1891) they are guaranteed to have at least one perfect matching. However, in this case more is known: the duals of Apollonian networks always have an exponential number of perfect matchings. [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.

Power law graphs

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. They used these networks to model packings of space by particles of varying sizes. Based on their work, other authors introduced random Apollonian networks, formed by repeatedly choosing a random face to subdivide, and they showed that these also obey power laws in their degree distribution [17] and have small average distances. [18] Alan M. Frieze and Charalampos E. Tsourakakis analyzed the highest degrees and the eigenvalues of random Apollonian networks. [19] Andrade et al. also observed that their networks satisfy the small world effect, that all vertices are within a small distance of each other. Based on numerical evidence they estimated the average distance between randomly selected pairs of vertices in an n-vertex network of this type to be proportional to (log n)3/4, but later researchers showed that the average distance is actually proportional to log n. [20]

Angle distribution

Butler & Graham (2010) observed that if each new vertex is placed at the incenter of its triangle, so that the edges to the new vertex bisect the angles of the triangle, then the set of triples of angles of triangles in the subdivision, when reinterpreted as triples of barycentric coordinates of points in an equilateral triangle, converges in shape to the Sierpinski triangle as the number of levels of subdivision grows.

Hamiltonicity

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]

Enumeration

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. Thus, the numbers of Apollonian networks (with a fixed outer triangle) on 3, 4, 5, ... vertices are:

1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... (sequence A001764 in the OEIS ),

a sequence that also counts ternary trees and dissections of convex polygons into odd-sided polygons. For instance, there are 12 6-vertex Apollonian networks: three formed by subdividing the outer triangle once and then subdividing two of the resulting triangles, and nine formed by subdividing the outer triangle once, subdividing one of its triangles, and then subdividing one of the resulting smaller triangles.

History

Birkhoff (1930) is an early paper that uses a dual form of Apollonian networks, the planar maps formed by repeatedly placing new regions at the vertices of simpler maps, as a class of examples of planar maps with few colorings.

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. In graph theory, the close connection between planarity and treewidth goes back to Robertson & Seymour (1984), who showed that every minor-closed family of graphs either has bounded treewidth or contains all of the planar graphs. 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.

The name "Apollonian network" was given by Andrade et al. (2005) to the networks they studied in which the level of subdivision of triangles is uniform across the network; these networks correspond geometrically to a type of stacked polyhedron called a Kleetope. [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. [18] The triangulations generated in this way have also been named "stacked triangulations" [23] or "stack-triangulations". [24]

See also

Notes

  1. ↑ This graph is named after the work of Goldner & Harary (1975); however, it appears earlier in the literature, for instance in Grünbaum (1967), p. 357.
  2. ↑ The equivalence of planar 3-trees and chordal maximal planar graphs was stated without proof by Patil (1986). For a proof, see Markenzon, Justel & Paciornik (2006). For a more general characterization of chordal planar graphs, and an efficient recognition algorithm for these graphs, see Kumar & Madhavan (1989). The observation that every chordal polyhedral graph is maximal planar was stated explicitly by Gerlach (2004).
  3. ↑ Fowler (1998).
  4. ↑ 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 Birkhoff (1930).
  5. ↑ Felsner & Zickfeld (2008); Bernardi & Bonichon (2009).
  6. ↑ 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 Arnborg, Proskurowski & Corniel (1986) and Bodlaender (1998). For direct proofs that the octahedral graph and the pentagonal-prism graph are the only two planar forbidden minors, see Dai & Sato (1990) and El-Mallah & Colbourn (1990).
  7. ↑ Politof (1983) 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 El-Mallah & Colbourn (1990).
  8. ↑ For the characterization in terms of the maximum number of triangles in a planar graph, see Hakimi & Schmeichel (1979). Alon & Caro (1984) 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 Wood (2007), who provides an Apollonian network as an example showing that this bound is tight. For generalizations of these bounds to nonplanar surfaces, see Dujmović et al. (2009).
  9. ↑ Andrade et al. (2005).
  10. ↑ Thurston (1978–1981).
  11. ↑ See, e.g., Below, De Loera & Richter-Gebert (2000).
  12. ↑ Demaine & Schulz (2011).
  13. ↑ Biedl & Ruiz Velázquez (2010).
  14. ↑ For subdividing a triangle with rational side lengths so that the smaller triangles also have rational side lengths, see Almering (1963). For progress on the general problem of finding planar drawings with rational edge lengths, see Geelen, Guo & McKinnon (2008).
  15. ↑ For the drawings with integer coordinates, see Mondal et al. (2010), and for the drawings on a given vertex set, see Nishat, Mondal & Rahman (2011).
  16. ↑ Jiménez & Kiwi (2010).
  17. ↑ Tsourakakis (2011)
  18. 1 2 Zhou et al. (2004); Zhou, Yan & Wang (2005).
  19. ↑ Frieze & Tsourakakis (2011)
  20. ↑ Albenque & Marckert (2008);Zhang et al. (2008).
  21. ↑ See Nishizeki (1980) for a 1-tough non-Hamiltonian example, Böhme, Harant & Tkáč (1999) for the proof that Apollonian networks with greater toughness are Hamiltonian, and Gerlach (2004) for an extension of this result to a wider class of planar graphs.
  22. ↑ Grünbaum (1963); Grünbaum (1967).
  23. ↑ Alon & Caro (1984); Zickfeld & Ziegler (2006); Badent et al. (2007); Felsner & Zickfeld (2008).
  24. ↑ Albenque & Marckert (2008); Bernardi & Bonichon (2009); Jiménez & Kiwi (2010).

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Complete graph</span> Graph in which every two vertices are adjacent

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Outerplanar graph</span> Non-crossing graph with vertices on outer face

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

<span class="mw-page-title-main">Clique (graph theory)</span> Subset of the vertices of a node-link graph that are all adjacent to each other

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

<span class="mw-page-title-main">Complete bipartite graph</span> Bipartite graph where each node of 1st set is linked to all nodes of 2nd set

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

<span class="mw-page-title-main">Cograph</span> Graph formed by complementation and disjoint union

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

<span class="mw-page-title-main">Polyhedral graph</span> Graph made from vertices and edges of a convex polyhedron

In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.

<span class="mw-page-title-main">Herschel graph</span> Bipartite non-Hamiltonian polyhedral graph

In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph, and is the smallest polyhedral graph that does not have a Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs.

<span class="mw-page-title-main">Goldner–Harary graph</span> Undirected graph with 11 nodes and 27 edges

In the mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after A. Goldner and Frank Harary, who proved in 1975 that it was the smallest non-Hamiltonian maximal planar graph. The same graph had already been given as an example of a non-Hamiltonian simplicial polyhedron by Branko Grünbaum in 1967.

In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length in G has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

<span class="mw-page-title-main">Block graph</span> Graph whose biconnected components are all cliques

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique.

<span class="mw-page-title-main">K-tree</span>

In graph theory, a k-tree is an undirected graph formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex v has exactly k neighbors U such that, together, the k + 1 vertices formed by v and U form a clique.

<span class="mw-page-title-main">Well-covered graph</span> Graph with equal-size maximal independent sets

In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970.

In polyhedral combinatorics, a stacked polytope is a polytope formed from a simplex by repeatedly gluing another simplex onto one of its facets.

In graph theory, a class of graphs is said to have few cliques if every member of the class has a polynomial number of maximal cliques. Certain generally NP-hard computational problems are solvable in polynomial time on such classes of graphs, making graphs with few cliques of interest in computational graph theory, network analysis, and other branches of applied mathematics. Informally, a family of graphs has few cliques if the graphs do not have a large number of large clusters.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.