<p>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</p>

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

<p>and</p>

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

CC BY-SA 3.0
2015-03-17T14:35:49.857Z
2015-03-17T14:35:49.857Z
David Eppstein
<p>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 <a href="http://jgaa.info/accepted/99/Eppstein99.3.3.pdf">Subgraph Isomorphism in Planar Graphs and Related Problems</a> by David Eppstein of 1999; see Theorem 1. The paper indeed uses treewidth techniques.</p>

CC BY-SA 3.0
2015-03-17T11:16:07.080Z
2015-03-17T23:04:28.953Z
2015-03-17T23:04:28.953Z
Bart Jansen
<p>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:</p>

<ul>
<li>What is a reference for this procedure?</li>
<li>Can the time be made linear?</li>
</ul>

<p>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.</p>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2015-03-16T16:03:31.623Z
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.
Ryan Williams
CC BY-SA 3.0
2015-03-16T16:40:55.010Z
@RyanWilliams You are correct, of course! I will update the question.
SamiD
<reference-request><graph-algorithms><planar-graphs>
Time complexity of counting triangles in planar graphs
SamiD
# Time complexity of counting triangles in planar graphs

(Asked by: username_0 on 2015-03-15)

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.

**Tags:** reference-request, graph-algorithms, planar-graphs

> **Comments:**
> **username_1**: 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.  
> **username_0**: @RyanWilliams You are correct, of course! I will update the question.  

---

## 2 answers

### Answer by username_3 on 2015-03-17. Score: 22 | Accepted answer

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](http://jgaa.info/accepted/99/Eppstein99.3.3.pdf) by username_2 of 1999; see Theorem 1. The paper indeed uses treewidth techniques.


---

### Answer by username_2 on 2015-03-17. Score: 21

Although username_3'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.


---

