Information Technology Reference
In-Depth Information
(
,
)
=
We use the following corollary that we get if we substitute
Q
x
y
x
and
(
,
)
=
P
x
y
0 in Green's theorem.
Corollary 5
(Area by line integrals)
Let C be a closed, piecewise smooth, simple
curve on the plane that is oriented counterclockwise. Let R
C
be the region bounded
by C . Then,
Area
(
R
C
)
=
xdy
.
C
Theorem 6
[
TV12
]
There is a log-space algorithm that, given any planar graph G,
assigns weights to the edges so that the resulting weighted graph is min-unique.
Let us assume that the planar graph
G
=
(
V
,
E
)
is presented as a straight-line
drawing. That is, each vertex
v
is represented as a point
(
x
v
,
y
v
)
in the plane so that
(
,v)
(
x
u
,
y
u
)
(
x
v
,
y
v
)
an edge
. In addition, no such
lines intersect other than at the vertices. Moreover, we assume that the coordinates
are integer points with values bounded by poly
u
is a line between points
and
(
n
is the number of vertices).
Typically, planar graphs are presented as a combinatorial embedding and it is not
clear how such line drawings can be computed in log-space from a combinatorial
embedding. However, this is not critical and in [
TV12
] we show how to handle this
presentation issue.
Let
e
(
n
)
=
(
u
,v)
be a directed edge directed from
u
to
v
where
u
is identified with
the point
(
x
u
,
y
u
)
and
v
is identified with
(
x
v
,
y
v
)
. For such a directed edge, define
a weight function
w
as follows:
w
g
t
(
e
)
=
2
×
xdy
=
(
y
v
−
y
u
)(
x
v
+
x
u
)
e
The required isolation property of the weight function is proved using the following
crucial lemma.
Lemma 7
Let G be a directed planar graph and let C be any directed simple cycle
in G. Let R
C
be the region enclosed by C . Then the weight of the cycle C ,
|
w
g
t
(
C
)
|=
2
×
Area
(
R
c
)
. In particular,
w
g
t
(
C
)
is nonzero.
Proof
Let
C
=
(
e
1
,
e
2
,...,
e
l
)
be a directed cycle-oriented counterclockwise. Then
we have
w
g
t
(
C
)
=
w
g
t
(
e
i
)
=
2
×
xdy
=
2
×
xdy
=
2
×
Area
(
R
C
)
e
i
C
i
i
The third equality follows from the linearity of integrals and the last equality follows
fromCorollary 7. If
C
is oriented clockwise, we get that
w
g
t
(
C
)
=−
2
×
Area
(
R
C
)
.
Hence the lemma.