Packings of cuts realizing distances between certain vertices in a planar graph
✍ Scribed by A.V. Karzanov
- Publisher
- Elsevier Science
- Year
- 1990
- Tongue
- English
- Weight
- 958 KB
- Volume
- 85
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
Recently A. Schrijver proved the following theorem. Suppose that G = (V, E) is a connected planar graph embedded in the euclidean plane, that 0 and Z are two of its faces, and that the edges e E E have nonnegative integer-valued lengths Z(e) such that the length of each circuit in G is even. Then there exist cuts B,, . , B, in G weighted by nonnegative integer-valued weights I,, . , I, so that: (i) for each e E E, the sum of the weights of the cuts containing e does not exceed Z(e), and (ii) for each two vertices s and t both in the boundary of 0 or in the boundary of I, the sum of the weights of the cuts 'separating' s and t is equal to the distance between s and t.
We given another proof of this theorem which provides a strongly polynomial-time algorithm for finding such cuts and weights.