Green's theorem and isolation in planar graphs
We show a simple application of Green's theorem from multivariable calculus to the isolation problem in planar graphs. In particular, we give a log-space construction of a skew-symmetric, polynomially-bounded edge weight function for directed planar graphs, such that the weight of any simple cycle in the graph is non-zero with respect to this weight function. As a direct consequence of the above weight function, we are able to isolate a directed path between two fixed vertices, in a directed planar graph. We also show that given a bipartite planar graph, we can obtain an edge weight function (using the above function) in log-space, which isolates a perfect matching in the given graph. Earlier this was known to be true only for grid graphs - which is a proper subclass of planar graphs. We also look at the problem of obtaining a straight line embedding of a planar graph in log-space. Although we do not quite achieve this goal, we give a piecewise straight line embedding of the given planar graph in log-space. Crown Copyright (C) 2012 Published by Elsevier Inc. All rights reserved.
green's theorem space complexity isolating lemma