Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-151 | 30th September 2010 19:33

Green’s Theorem and Isolation in Planar Graphs


Authors: Raghunath Tewari, N. V. Vinodchandran
Publication: 1st October 2010 13:38
Downloads: 3454


We show a simple application of Green’s theorem from multivariable calculus to the isolation problem in planar graphs. In particular, we construct a skew-symmetric, polynomially bounded, edge weight function for a directed planar graph in logspace 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 logspace, 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 logspace. Although we do not quite achieve this goal, we give a piecewise straight line embedding of the given planar graph in logspace.

ISSN 1433-8092 | Imprint