15
$\begingroup$

Counting triangles in general graphs can be done trivially in $O(n^3)$ time and I think that doing much faster is hard (references welcome). What about planar graphs? The following straightforward procedure shows that it can be done in $O(n\log{n})$ time. My question is two-fold:

  • What is a reference for this procedure?
  • Can the time be made linear?

From the algorithmic proof of Lipton-Tarjan's planar separator theorem we can, in time linear in the size of the graph, find a partition of vertices of the graph into three sets $A,B,S$ such that there are no edges with one endpoint in $A$ and the other in $B$, $S$ has size bounded by $O(\sqrt{n})$ and both $A,B$ have sizes upper bounded by $\frac{2}{3}$ of the number of vertices. Notice that any triangle in the graph either lies entirely inside $A$ or entirely inside $B$ or uses at least one vertex of $S$ with the other two vertices from $A \cup S$ or both from $B \cup S$. Thus it suffices to count the number of triangles in the graph on $S$ and the neighbours of $S$ in $A$ (and similarly for $B$). Notice that $S$ and its $A$-neighbours induce a $k$-outer planar graph (the said graph is a subgraph of a planar graph of diameter $4$). Thus counting the number of triangles in such a graph can be done directly by dynamic programming or by an application of Courcelle's theorem (I know for sure that such a counting version exists in the Logspace world by Elberfeld et al and am guessing that it also exists in the linear time world) since forming an undirected triangle is an $\mathsf{MSO}_1$ property and since a bounded width tree decomposition is easy to obtain from an embedded $k$-outer planar graph.

Thus we have reduced the problem to a pair of problems which are each a constant fraction smaller at the expense of a linear time procedure.

Notice that the procedure can be extended to find the count of the number of instances of any fixed connected graph inside an input graph in $O(n\log{n})$ time.

$\endgroup$
  • 6
    $\begingroup$ You can count triangles in general graphs by taking the adjacency matrix $A$ and computing $tr(A^3)/6$. This takes $n^{\omega}$ time, where $\omega < 2.373$ is the matrix multiplication exponent. $\endgroup$ – Ryan Williams Mar 16 '15 at 16:03
  • $\begingroup$ @RyanWilliams You are correct, of course! I will update the question. $\endgroup$ – SamiD Mar 16 '15 at 16:40
19
$\begingroup$

The number of occurrences of any fixed subgraph H in a planar graph G can be counted in O(n) time, even if H is disconnected. This, and several related results, are described in the paper Subgraph Isomorphism in Planar Graphs and Related Problems by David Eppstein of 1999; see Theorem 1. The paper indeed uses treewidth techniques.

$\endgroup$
18
$\begingroup$

Although Bart Jansen's answer solves the general case of subgraph counting, the problem of counting (or listing) all triangles in a planar graph (or more generally any graph of bounded arboricity) has been known to be linear time for much longer. See

C. Papadimitriou and M. Yannakakis, The clique problem for planar graphs, Inform. Proc. Letters 13 (1981), pp. 131–133.

and

N. Chiba and T.Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput. 14 (1985), pp. 210–223.

$\endgroup$

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.