ECCC-Report TR10-151https://eccc.weizmann.ac.il/report/2010/151Comments and Revisions published for TR10-151en-usFri, 01 Oct 2010 13:38:17 +0200
Paper TR10-151
| Green’s Theorem and Isolation in Planar Graphs |
Raghunath Tewari,
N. V. Vinodchandran
https://eccc.weizmann.ac.il/report/2010/151We 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.Fri, 01 Oct 2010 13:38:17 +0200https://eccc.weizmann.ac.il/report/2010/151