# Cholesky factorization of planar graphs

Suppose the sparsity pattern of $A \in \mathbb{R}^{N \times N}$ is a planar graph. Can I use this to bound the complexity of solving

$$Ax = b$$ ?

In particular, I was hoping to use the planar separator theorem to produce an elimination ordering that would give an $O(N \sqrt N)$ factorization time.

Yes. As this book chapter (by S. Toledo) shows, the number of arithmetic operations is bounded by the sum over the non-zero columns of the squares of the numbers of nonzero elements therein. The sum of squares of degrees is called "The first Zagreb index", which you can google to gain further enlightenment.

• I was actually hoping to use the planarity of the graph to give a tighter lower bound. Perhaps there is a connection here to the first Zagreb index and I'm just not seeing it? – Alex Flint Aug 5 '17 at 23:46
• The average degree of a planar triangulation is $6,$ so that helps a fair bit. – Igor Rivin Aug 6 '17 at 0:50