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.
Search WWH ::




Custom Search