2
$\begingroup$

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.

enter image description here

$\endgroup$

1 Answer 1

4
$\begingroup$

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 /@ %

enter image description here

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – licheng
    Jan 11 at 13:36
  • 1
    $\begingroup$ @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? $\endgroup$
    – Szabolcs
    Jan 11 at 14:12
  • $\begingroup$ 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. $\endgroup$
    – licheng
    Jan 11 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.