Green's theorem and isolation in planar graphs
Green's theorem and isolation in planar graphs
复制标题
格林定理和平面图中的孤立
DOI：
10.1016/j.ic.2012.03.002
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
N. V. Vinodchandran
中科院分区：
文献类型：
--
作者：
Raghunath Tewari;N. V. Vinodchandran
我们展示了格林定理从多变量微积分到平面图中的隔离问题的简单应用。特别地，我们给出了有向平面图的斜对称、多项式有界边权重函数的对数空间构造，使得图中任何简单环的权重相对于该权重函数都是非零的。作为上述权重函数的直接结果，我们能够在有向平面图中隔离两个固定顶点之间的有向路径。我们还表明，给定二部平面图，我们可以在对数空间中获得边权重函数（使用上述函数），该函数在给定图中隔离了完美匹配。早些时候，人们知道这只适用于网格图——它是平面图的一个适当的子类。我们还研究了在对数空间中获得平面图的直线嵌入的问题。尽管我们没有完全实现这个目标，但我们给出了给定平面图在对数空间中的分段直线嵌入。
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.