<p>Using nested dissections you can even solve a linear system (based on a planar graph) in $O(\sqrt{n^\omega})$. This was for example noted in a <a href="http://arxiv.org/abs/0908.0488">paper</a>  I have with Günter Rote and Ares Ribó and in this <a href="http://www.tau.ac.il/~nogaa/PDFS/sparsesystem.pdf">paper by Alon and Yuster</a>. </p>

<p>The former paper also contains an approach how to compute the pairwise resistances between vertices on a a common face in $O(\sqrt{n^\omega})$. This <a href="http://arxiv.org/pdf/1203.1256v1.pdf">paper by Kenyon</a> might also contain helpful ideas.</p>

CC BY-SA 3.0
2013-02-14T22:20:45.177Z
2013-02-14T22:20:45.177Z
A.Schulz
<p>Consider an electrical network modeled as a planar graph G, where each edge represents a 1Ω resistor.  <strong>How quickly can we compute the <em>exact</em> effective resistance between two vertices in G?</strong>  Equivalently, how quickly can we compute the <em>exact</em> current flowing along each edge if we attach a 1V battery to two vertices in G? </p>

<p>Kirchhoff's well-known <a href="http://en.wikipedia.org/wiki/Kirchhoff%27s_circuit_laws">voltage and current laws</a> reduce this problem to solving a system of linear equations with one variable per edge.  More recent results — described explicitly by <a href="http://link.springer.com/article/10.1007%2FBF01164627">Klein and Randić (1993)</a> but implicit in earlier work of <a href="http://math.dartmouth.edu/~doyle/docs/walks/walks.pdf">Doyle and Snell (1984)</a> — reduce the problem to solving a linear system with one variable per vertex, representing that node's <em>potential</em>; the matrix for this linear system is the Laplacian matrix of the graph.</p>

<p>Either linear system can be solved exactly in $O(n^{3/2})$ time using nested dissection and planar separators [<a href="http://www.jstor.org/discover/10.2307/2156840?uid=3739656&amp;uid=2&amp;uid=4&amp;uid=3739256&amp;sid=21101650334243">Lipton Rose Tarjan 1979</a>].  <strong>Is this the fastest algorithm known?</strong></p>

<p>Recent seminal results of Spielman, Teng, and others imply that the Laplacian system in <em>arbitrary</em> graphs can be solved <em>approximately</em> in near-linear time.  See [<a href="http://arxiv.org/abs/1003.2958">Koutis Miller Peng 2010</a>] for the current best running time, and <a href="https://simonsfoundation.org/features/science-news/mathematics-and-physical-science/network-solutions/">this amazing article</a> by Erica Klarreich at the Simons Foundation for a high-level overview.  But I'm specifically interested in <em>exact</em> algorithms for <em>planar</em> graphs.</p>

<p>Assume a model of computation that supports exact real arithmetic in constant time.</p>

CC BY-SA 3.0
2013-02-14T19:25:21.543Z
the Klarreich article mentions applications in (optimizing) max flow near the end and is already out of date due to the recent Orlin $O(m \cdot n)$ breakthrough, which is apparently not related to the Laplacian direction of attack. see also this recent tcs.se question, [Are any of the state of the art Maximum Flow algorithms practical?](http://cstheory.stackexchange.com/questions/16347/)
vzn
<ds.algorithms><graph-theory><planar-graphs><physics>
Exact planar electrical flow
Jeffε
# Exact planar electrical flow

(Asked by: username_0 on 2013-02-14)

Consider an electrical network modeled as a planar graph G, where each edge represents a 1Ω resistor. **How quickly can we compute the *exact* effective resistance between two vertices in G?** Equivalently, how quickly can we compute the *exact* current flowing along each edge if we attach a 1V battery to two vertices in G?

Kirchhoff's well-known [voltage and current laws](http://en.wikipedia.org/wiki/Kirchhoff%27s_circuit_laws) reduce this problem to solving a system of linear equations with one variable per edge. More recent results — described explicitly by [Klein and Randić (1993)](http://link.springer.com/article/10.1007%2FBF01164627) but implicit in earlier work of [Doyle and Snell (1984)](http://math.dartmouth.edu/~doyle/docs/walks/walks.pdf) — reduce the problem to solving a linear system with one variable per vertex, representing that node's *potential*; the matrix for this linear system is the Laplacian matrix of the graph.

Either linear system can be solved exactly in $O(n^{3/2})$ time using nested dissection and planar separators [[Lipton Rose Tarjan 1979](http://www.jstor.org/discover/10.2307/2156840?uid=3739656&uid=2&uid=4&uid=3739256&sid=21101650334243)]. **Is this the fastest algorithm known?**

Recent seminal results of Spielman, Teng, and others imply that the Laplacian system in *arbitrary* graphs can be solved *approximately* in near-linear time. See [[Koutis Miller Peng 2010](http://arxiv.org/abs/1003.2958)] for the current best running time, and [this amazing article](https://simonsfoundation.org/features/science-news/mathematics-and-physical-science/network-solutions/) by Erica Klarreich at the Simons Foundation for a high-level overview. But I'm specifically interested in *exact* algorithms for *planar* graphs.

Assume a model of computation that supports exact real arithmetic in constant time.

**Tags:** ds.algorithms, graph-theory, planar-graphs, physics
> **Comments:**
> **username_1**: the Klarreich article mentions applications in (optimizing) max flow near the end and is already out of date due to the recent Orlin $O(m \cdot n)$ breakthrough, which is apparently not related to the Laplacian direction of attack. see also this recent tcs.se question, [Are any of the state of the art Maximum Flow algorithms practical?](http://cstheory.stackexchange.com/questions/16347/)  

---

## 1 answers

### Answer by username_2 on 2013-02-14. Score: 14

Using nested dissections you can even solve a linear system (based on a planar graph) in $O(\sqrt{n^\omega})$. This was for example noted in a [paper](http://arxiv.org/abs/0908.0488) I have with Günter Rote and Ares Ribó and in this [paper by Alon and Yuster](http://www.tau.ac.il/~nogaa/PDFS/sparsesystem.pdf).

The former paper also contains an approach how to compute the pairwise resistances between vertices on a a common face in $O(\sqrt{n^\omega})$. This [paper by Kenyon](http://arxiv.org/pdf/1203.1256v1.pdf) might also contain helpful ideas.


---

