How to determine that a plane graph is an Apollonian network

A planar graph $$G$$ is an Apollonian network if it is isomorphic to $$K_3$$ or it contains a vertex $$v$$ of degree $$3$$ such that $$G-v$$ is an Apollonian network. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs. And every uniquely 4-colorable planar graph is an Apollonian network. Based on the above facts, we can count the number of 4-coloring for the graph to determine, but it should not be efficient.

For a graph G with $$V (G) = \{v_1,v_2,\cdots v_n\}$$, say, and a positive integer $$\lambda$$, the number of different proper $$\lambda$$-colorings of $$G$$ is denoted by $$P(G; \lambda)$$ and is called the chromatic polynomial of $$G$$. Thus, a $$4$$-chromatic graph $$G$$ is uniquely $$4$$-colorable if and only if $$P(G; 4) = 4!$$.

ApolloniannetworkQ[g_] := If[ChromaticPolynomial[g, 4] == 24, True, False]
g = GraphData["GoldnerHararyGraph"];
ApolloniannetworkQ[g]


It may not be algorithmically efficient to compute ChromaticPolynomial of a graph. I don't know if there is a good way to determine whether a plane graph is an Apollonian network.

According to Wikipedia, a graph is Apollonian if it is chordal and maximal planar. IGraph/M implements checks for these. Thus we can use

Needs["IGraphM"]
apollonianQ[g_?UndirectedGraphQ] := IGChordalQ[g] && IGMaximalPlanarQ[g]


Let us generate a few non-isomorphic Apollonian networks on v=8 vertices using rejection sampling:

v = 8;
Table[
IGTryUntil[apollonianQ]@RandomGraph[{v, 3 v - 6}],
100
] // DeleteDuplicatesBy[IGBlissCanonicalGraph]


Plot them as planar graphs:

IGLayoutPlanar /@ %


• It's really cool. But I'm not sure that your function IGChordalQ is very efficient . I was going to do it by definition of Apollonian network, recursively, but it's probably inefficient. Jan 11, 2022 at 13:36
• @licheng It uses igraph_is_chordal, it should be linear in number of vertices + number of edges. The bottleneck is probably in the planarity testing with this approach. Anyway, this will certainly be vastly more efficient than anything with ChormaticPolynomial`. Do you have an example of a graph where it runs too slowly? Jan 11, 2022 at 14:12
• Thanks for your nice explanation for the IGChordalQ. I think your answer is nice enough. At the moment I don't have any examples to react it's not fast enough. Jan 11, 2022 at 14:58