TR10-151 Authors: Raghunath Tewari, Vinodchandran Variyam

Publication: 1st October 2010 13:38

Downloads: 2504

Keywords:

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.