Dual map

Dual map --- двойственная карта.

A dual map of a connected planar graph [math]\displaystyle{ G }[/math] is the map [math]\displaystyle{ G^{\ast} }[/math] constructed as follows. We select a point [math]\displaystyle{ x_{F} }[/math] in each of the faces [math]\displaystyle{ F }[/math] of [math]\displaystyle{ G }[/math]; these will be the vertices of [math]\displaystyle{ G^{\ast} }[/math]. Also we select a point [math]\displaystyle{ p_{e} }[/math] on each edge [math]\displaystyle{ e }[/math] of [math]\displaystyle{ G }[/math]. We connect each point [math]\displaystyle{ p_{e} }[/math] to the points [math]\displaystyle{ x_{F}, x_{F'} }[/math] by Jordan curves [math]\displaystyle{ J_{e}, J'_{e} }[/math] interior to [math]\displaystyle{ F }[/math] and [math]\displaystyle{ F' }[/math], respectively, where [math]\displaystyle{ F, F' }[/math] are two faces adjacent to [math]\displaystyle{ e }[/math]. If [math]\displaystyle{ F = F' }[/math] (i.e. the same face of [math]\displaystyle{ G }[/math] bounds [math]\displaystyle{ e }[/math] from both sides), then [math]\displaystyle{ J_{e}, J'_{e} }[/math] should connect [math]\displaystyle{ p_{e} }[/math] to [math]\displaystyle{ x_{F} }[/math] such that they leave [math]\displaystyle{ p_{e} }[/math] on different sides of [math]\displaystyle{ e }[/math] (this happens, if [math]\displaystyle{ e }[/math] is a cutting edge. Moreover, let us choose [math]\displaystyle{ J_{e}, J'_{e} }[/math] such that the arcs [math]\displaystyle{ J_{e} }[/math] connecting [math]\displaystyle{ X_{F} }[/math] to points [math]\displaystyle{ p_{e} }[/math] on the boundary of [math]\displaystyle{ F }[/math] should have no point in common other than [math]\displaystyle{ x_{F} }[/math]. Set [math]\displaystyle{ e^{\ast} = J_{e} \cup J'_{e} }[/math] and [math]\displaystyle{ E(G^{\ast}) = \{e^{\ast}: \; e \in E(G)\} }[/math]. Then [math]\displaystyle{ G^{\ast} }[/math] is a planar map and is, essentially, uniquely defined, i.e. if [math]\displaystyle{ \hat{G}^{\ast} }[/math] is another dual map of [math]\displaystyle{ G }[/math], then there is a homeomorphism [math]\displaystyle{ \varphi }[/math] of the plane onto itself such that [math]\displaystyle{ \varphi(x) = x }[/math] for each [math]\displaystyle{ x \in V(G) }[/math], [math]\displaystyle{ \varphi(e) = e }[/math] for each [math]\displaystyle{ e \in E(G) }[/math], [math]\displaystyle{ \varphi(V(G^{\ast})) = V(\hat{G}^{\ast}) }[/math] and if [math]\displaystyle{ \hat{e}^{\ast} }[/math] is the edge corresponding to [math]\displaystyle{ e^{\ast} }[/math] in [math]\displaystyle{ \hat{G}^{\ast} }[/math], then [math]\displaystyle{ \varphi(e^{\ast}) = \hat{e}^{\ast} }[/math]. The dual of [math]\displaystyle{ G^{\ast} }[/math] is [math]\displaystyle{ G }[/math]. The above construction and these last assertions involve much from plane topology that we accept here without proof.