\manpage {planar\_map} {} {Planar Maps} 
 
\definition
    An instance $M$ of the data type $planar\_map$ is the combinatorial
    embedding of a planar graph, i.e., $M$ is bidirected (for every edge
    $(v,w)$ of $M$ the reverse edge $(w,v)$ is also in $M$) and  
    there is a planar embedding of $M$ such that for every node $v$ the 
    ordering of the edges in the adjacency list of $v$ corresponds to the 
    counter-clockwise ordering of these edges around $v$ in the embedding.

    Planar maps make use of the item type $face$ in addition to nodes and
    edges.

 
\creation M 
 
\create {(graph\ G)}
   { creates an instance $M$ of type $planar\_map$ and initializes it to
    the planar map represented by the directed graph $G$. \precond $G$
    represents a bidirected planar map, i.e. for every edge $(v,w)$ in $G$
    the reverse edge $(w,v)$ is also in $G$ and there is a planar embedding
    of $G$ such that for every node $v$ the ordering of the edges in the
    adjacency list of $v$ corresponds to the counter-clockwise ordering of
    these edges around $v$ in the embedding. }
 
 
\operations 2 4.6
 
\op  list\<face\> all\_faces {()}
           {  returns the list of all faces of \var. }
 
 
\op  list\<face\> adj\_faces {(node\ v)}
           {  returns the list of all faces of \var\ adjacent
	     to node $v$ in counter-clockwise order. }
 
 
\op  face adj\_face {(edge\ e)}
           {  returns the face of \var\ to the right of $e$. }
 
 
\op  list\<node\> adj\_nodes {(face\ f)}
           {  returns the list of all nodes of \var\ adjacent
             to face $f$ in clockwise order. }
 
 
\op  list\<edge\> adj\_edges {(face)}
           {  returns the list of all edges of \var\ bounding
	     face $f$ in clockwise order. }
 
 
\op  edge reverse {(edge\ e)}
           {  returns the reversal of edge $e$ in \var.  }
 
 
\op  edge first\_face\_edge {(face\ f)}
           {  returns the first edge of face $f$ in \var.  }
 
 
\op  edge succ\_face\_edge {(edge\ e)}
           {  returns the successor edge of $e$ in face $f$
	     i.e., the next edge in clockwise order. }
 
 
\op  edge pred\_face\_edge {(edge\ e)}
           {  returns the predecessor edge of $e$ in face $f$,
             i.e., the next edge in counter-clockwise order. }
 
 
\opl edge new\_edge {(edge\ e1, \ edge\ e2)}
           {  inserts the edge $e=(source(e_1),source(e_2))$
	    and its reversal edge into $M$.\\ \precond
	    $e_1$ and $e_2$ are bounding the same face $F$.
	    The operation splits $F$ into two new faces. }
 
 
\op  void del\_edge {(edge\ e)}
           {  deletes the edge $e$ from \var. The two faces
	    adjacent to $e$ are united to one face. }
 
 
\op  edge split\_edge {(edge\ e)}
           {  splits edge $e=(v,w)$ and its reversal $r=(w,v)$
	    into edges $(v,u)$, $(u,w)$, $(w,u)$, and $(u,v)$.
	    Returns the edge $(u,w)$.  }
 
 
\op  node new\_node {( list\<edge\>\ el)}
           {  splits the face bounded by the edges in $el$ by
	    inserting a new node $u$ and connecting it to all
	    source nodes of edges in $el$.\\ \precond
	    all edges in $L$ bound the same face. }
 
 
\op  node new\_node {(face\ f)}
           {  splits face $f$ into triangles by inserting a new
	    node $u$ and connecting it to all nodes of $f$.
	    Returns $u$. }
 
 
\op  list\<edge\> triangulate {()}
           {  triangulates all faces of \var\ by inserting new
	    edges. The list of inserted edges is is returned. }
 
 
\opl int straight\_line\_embedding {(node\_array\<int\>\&\ x, \ node\_array\<int\>\&\ y)}
           {  computes a straight line embedding for $M$ with
	    integer coordinates $x[v]$, $y[v])$ in the
	    range $0\dots 2(n-1)$ for every node $v$ of $M$,
	    and returns the maximal used coordinate.  }
 
 

\bigskip
{\bf Iteration}

{\bf forall\_faces}($f,M$)
$\{$ ``the faces of $M$ are successively assigned to $f$" $\}$

{\bf forall\_adj\_edges}($e,f$) \\
\phantom{{\bf forall\_edges}($v,M$)}
$\{$ ``the edges adjacent to face $f$ are successively assigned to $e$" $\}$ 
 
\implementation
Planar maps are implemented by parameterized directed graphs.
All operations take constant time, except for new\_edge and del\_edge
which take time $O(f)$ where $f$ is the number of edges in the created
faces and triangulate and straight\_line\_embedding which take time $O(n)$
where $n$ is the current size (number of edges) of the planar map. 
 

\newpage

 
\manpage {PLANAR\_MAP} {vtype,ftype} {Parameterized Planar Maps}
 
\definition
A parameterized planar map $M$ is a planar map whose nodes and faces
contain additional (user defined) data. Every node  contains
an element of a data type $vtype$, called the node type of $M$ and every
face contains an element of a data type $ftype$ called the face type of
$M$. All operations of the data type $planar\_map$ are also defined for
instances of any parameterized planar\_map type. For parameterized
planar maps there are additional operations to access or update
the node and face entries.
 
\creation M 
 
\create {(GRAPH\<vtype,ftype\>\ G)}
   { creates an instance \var\ of type \name\ and initializes it to
the planar map represented by the parameterized directed graph $G$.
The node entries of $G$ are copied into the corresponding nodes of $M$
and every face $f$ of $M$ is assigned the information of one of its
bounding edges in $G$.  \precond $G$ represents a planar map.  }
 
 
\operations 1.5 4.5 
 
\op  vtype inf {(node\ v)}
           {  returns the information of node $v$  }
 
 
\op  ftype inf {(face\ f)}
           {  returns the information of face $f$  }
 
 
\arrop vtype\&  {node\ v}
         {  returns a reference to the information of node $v$  }
 
 
\arrop ftype\&  {face\ f}
         {  returns a reference to the information of face $f$  }
 
 
\op  void assign {(node\ v, vtype\ x)}
           {  makes $x$ the information of node $v$  }
 
 
\op  void assign {(face\ f, ftype\ x)}
           {  makes $x$ the information of face $f$  }
 
 
\opl edge new\_edge {(edge\ e1, \ edge\ e2, \ ftype\ y)}
           {  inserts the edge $e=(source(e_1),source(e_2))$
	     and its reversal edge $e'$ into $M$. \precond
	     $e_1$ and $e_2$ are bounding the same face $F$.
	     The operation splits $F$ into two new faces $f$,
	     adjacent to edge $e$ and $f'$, adjacent to edge
	     $e'$ with inf($f$) = inf ($F$) and inf($f'$) = $y$. }
 
 
\opl edge split\_edge {(edge\ e, \ vtype\ x)}
           {  splits edge $e=(v,w)$ and its reversal $r=(w,v)$
	    into edges $(v,u)$, $(u,w)$, $(w,u)$, and $(u,v)$.
            Assigns information $x$ to the created node $u$ and
	    returns the edge $(u,w)$.  }
 
 
\opl node new\_node {(list\<edge\>\&\ el, vtype\ x)}
           {  splits the face bounded by the edges in $el$ by
	    inserting a new node $u$ and connecting it to all
	    source nodes of edges in $el$. Assigns information $x$
            to $u$ and returns $u$. \precond all edges in $el$ bound 
            the same face. }
 
 
\opl node new\_node {(face\ f, vtype\ x)}
           {  splits face $f$ into triangles by inserting a new
              node $u$ with information $x$ and connecting it 
	      to all nodes of $f$. Returns $u$. }
 
 
\implementation
Parameterized planar maps are derived from planar maps. All additional 
operations for manipulating the node and edge contents take constant time.
 
