# HG changeset patch
# User deba
# Date 1192811071 0
# Node ID c97596611d59108de4cd46b381cee2a92b752122
# Parent  290e43cddc1ab11d20b99ab30d7eecc9dddd9f4a
Planar Grid Embedding

diff -r 290e43cddc1a -r c97596611d59 lemon/planarity.h
--- a/lemon/planarity.h	Fri Oct 19 15:21:07 2007 +0000
+++ b/lemon/planarity.h	Fri Oct 19 16:24:31 2007 +0000
@@ -18,7 +18,7 @@
 #ifndef LEMON_PLANARITY_H
 #define LEMON_PLANARITY_H
 
-/// \ingroup graph_prop
+/// \ingroup planar
 /// \file
 /// \brief Planarity checking, embedding
 
@@ -29,6 +29,8 @@
 #include <lemon/radix_sort.h>
 #include <lemon/maps.h>
 #include <lemon/path.h>
+#include <lemon/iterable_maps.h>
+#include <lemon/edge_set.h>
 
 
 namespace lemon {
@@ -134,11 +136,11 @@
 
   }
 
-  /// \ingroup  graph_prop
+  /// \ingroup planar
   ///
   /// \brief Planarity checking of an undirected simple graph
   ///
-  /// This class implements the Boyer-Myrvold algorithm for planar
+  /// This class implements the Boyer-Myrvold algorithm for planarity
   /// checking of an undirected graph. This class is a simplified
   /// version of the PlanarEmbedding algorithm class, and it does
   /// provide neither embedding nor kuratowski subdivisons.
@@ -146,7 +148,7 @@
   class PlanarityChecking {
   private:
     
-    UGRAPH_TYPEDEFS(typename UGraph)
+    UGRAPH_TYPEDEFS(typename UGraph);
       
     const UGraph& _ugraph;
 
@@ -522,7 +524,7 @@
 
   };
 
-  /// \ingroup graph_prop
+  /// \ingroup planar
   ///
   /// \brief Planar embedding of an undirected simple graph
   ///
@@ -541,7 +543,7 @@
   class PlanarEmbedding {
   private:
     
-    UGRAPH_TYPEDEFS(typename UGraph)
+    UGRAPH_TYPEDEFS(typename UGraph);
       
     const UGraph& _ugraph;
     typename UGraph::template EdgeMap<Edge> _embedding;
@@ -586,6 +588,9 @@
 
   public:
 
+    /// \brief The map for store of embedding
+    typedef typename UGraph::template EdgeMap<Edge> EmbeddingMap;
+
     /// \brief Constructor
     ///
     /// \warining The graph should be simple, i.e. parallel and loop edge
@@ -701,6 +706,14 @@
       return _embedding[edge];
     }
 
+    /// \brief Gives back the calculated embedding map
+    ///
+    /// The returned map contains the successor of each edge in the
+    /// graph.
+    const EmbeddingMap& embedding() const {
+      return _embedding;
+    }
+
     /// \brief Gives back true when the undirected edge is in the
     /// kuratowski subdivision
     ///
@@ -1806,6 +1819,623 @@
 
   };
 
+  namespace _planarity_bits {
+
+    template <typename UGraph, typename EmbeddingMap>
+    void makeConnected(UGraph& ugraph, EmbeddingMap& embedding) {
+      DfsVisitor<UGraph> null_visitor;
+      DfsVisit<UGraph, DfsVisitor<UGraph> > dfs(ugraph, null_visitor);
+      dfs.init();
+
+      typename UGraph::Node u = INVALID;
+      for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) {
+	if (!dfs.reached(n)) {
+	  dfs.addSource(n);
+	  dfs.start();
+	  if (u == INVALID) {
+	    u = n;
+	  } else {
+	    typename UGraph::Node v = n;
+	    
+	    typename UGraph::Edge ue = typename UGraph::OutEdgeIt(ugraph, u);
+	    typename UGraph::Edge ve = typename UGraph::OutEdgeIt(ugraph, v);
+
+	    typename UGraph::Edge e = ugraph.direct(ugraph.addEdge(u, v), true);
+	    
+	    if (ue != INVALID) {
+	      embedding[e] = embedding[ue];
+	      embedding[ue] = e;
+	    } else {
+	      embedding[e] = e;
+	    }
+
+	    if (ve != INVALID) {
+	      embedding[ugraph.oppositeEdge(e)] = embedding[ve];
+	      embedding[ve] = ugraph.oppositeEdge(e);
+	    } else {
+	      embedding[ugraph.oppositeEdge(e)] = ugraph.oppositeEdge(e);
+	    }
+	  }
+	}
+      }
+    }
+
+    template <typename UGraph, typename EmbeddingMap>
+    void makeBiNodeConnected(UGraph& ugraph, EmbeddingMap& embedding) {
+      typename UGraph::template EdgeMap<bool> processed(ugraph);
+
+      std::vector<typename UGraph::Edge> edges;
+      for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) {
+	edges.push_back(e);
+      }
+
+      IterableBoolMap<UGraph, typename UGraph::Node> visited(ugraph, false);
+      
+      for (int i = 0; i < int(edges.size()); ++i) {
+	typename UGraph::Edge pp = edges[i];
+	if (processed[pp]) continue;
+
+	typename UGraph::Edge e = embedding[ugraph.oppositeEdge(pp)];
+	processed[e] = true;
+	visited.set(ugraph.source(e), true);
+	
+	typename UGraph::Edge p = e, l = e;
+	e = embedding[ugraph.oppositeEdge(e)];
+	
+	while (e != l) {
+	  processed[e] = true;
+
+	  if (visited[ugraph.source(e)]) {
+	    
+	    typename UGraph::Edge n = 
+	      ugraph.direct(ugraph.addEdge(ugraph.source(p), 
+					   ugraph.target(e)), true);
+	    embedding[n] = p;
+	    embedding[ugraph.oppositeEdge(pp)] = n;
+
+	    embedding[ugraph.oppositeEdge(n)] = 
+	      embedding[ugraph.oppositeEdge(e)];
+	    embedding[ugraph.oppositeEdge(e)] = 
+	      ugraph.oppositeEdge(n);
+	    
+	    p = n;
+	    e = embedding[ugraph.oppositeEdge(n)];
+	  } else {
+	    visited.set(ugraph.source(e), true);
+	    pp = p;
+	    p = e;
+	    e = embedding[ugraph.oppositeEdge(e)];
+	  }
+	}
+	visited.setAll(false);
+      }
+    }
+    
+    
+    template <typename UGraph, typename EmbeddingMap>
+    void makeMaxPlanar(UGraph& ugraph, EmbeddingMap& embedding) {
+      
+      typename UGraph::template NodeMap<int> degree(ugraph);
+
+      for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) {
+	degree[n] = countIncEdges(ugraph, n);
+      }
+
+      typename UGraph::template EdgeMap<bool> processed(ugraph);
+      IterableBoolMap<UGraph, typename UGraph::Node> visited(ugraph, false);
+
+      std::vector<typename UGraph::Edge> edges;
+      for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) {
+	edges.push_back(e);
+      }
+
+      for (int i = 0; i < int(edges.size()); ++i) {
+	typename UGraph::Edge e = edges[i];
+
+	if (processed[e]) continue;
+	processed[e] = true;
+
+	typename UGraph::Edge mine = e;
+	int mind = degree[ugraph.source(e)];
+
+	int face_size = 1;	
+
+	typename UGraph::Edge l = e;
+	e = embedding[ugraph.oppositeEdge(e)];
+	while (l != e) {
+	  processed[e] = true;
+
+	  ++face_size;
+
+	  if (degree[ugraph.source(e)] < mind) {
+	    mine = e;
+	    mind = degree[ugraph.source(e)];
+	  }
+	  
+	  e = embedding[ugraph.oppositeEdge(e)];	  
+	}
+	
+	if (face_size < 4) {
+	  continue;
+	}
+
+	typename UGraph::Node s = ugraph.source(mine);
+	for (typename UGraph::OutEdgeIt e(ugraph, s); e != INVALID; ++e) {
+	  visited.set(ugraph.target(e), true); 
+	}
+
+	typename UGraph::Edge oppe = INVALID;
+
+	e = embedding[ugraph.oppositeEdge(mine)];
+	e = embedding[ugraph.oppositeEdge(e)];
+	while (ugraph.target(e) != s) {
+	  if (visited[ugraph.source(e)]) {
+	    oppe = e;
+	    break;
+	  }
+	  e = embedding[ugraph.oppositeEdge(e)];
+	}
+	visited.setAll(false);
+	
+	if (oppe == INVALID) {
+
+	  e = embedding[ugraph.oppositeEdge(mine)];
+	  typename UGraph::Edge pn = mine, p = e;
+
+	  e = embedding[ugraph.oppositeEdge(e)];
+	  while (ugraph.target(e) != s) {
+	    typename UGraph::Edge n = 
+	      ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true);
+
+	    embedding[n] = pn;
+	    embedding[ugraph.oppositeEdge(n)] = e;
+	    embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
+
+	    pn = n;
+	    
+	    p = e;
+	    e = embedding[ugraph.oppositeEdge(e)];
+	  }
+
+	  embedding[ugraph.oppositeEdge(e)] = pn;
+
+	} else {
+
+	  mine = embedding[ugraph.oppositeEdge(mine)];
+	  s = ugraph.source(mine);
+	  oppe = embedding[ugraph.oppositeEdge(oppe)];
+	  typename UGraph::Node t = ugraph.source(oppe);
+	  
+	  typename UGraph::Edge ce = ugraph.direct(ugraph.addEdge(s, t), true);
+	  embedding[ce] = mine;
+	  embedding[ugraph.oppositeEdge(ce)] = oppe;
+
+	  typename UGraph::Edge pn = ce, p = oppe;	  
+	  e = embedding[ugraph.oppositeEdge(oppe)];
+	  while (ugraph.target(e) != s) {
+	    typename UGraph::Edge n = 
+	      ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true);
+
+	    embedding[n] = pn;
+	    embedding[ugraph.oppositeEdge(n)] = e;
+	    embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
+
+	    pn = n;
+	    
+	    p = e;
+	    e = embedding[ugraph.oppositeEdge(e)];
+	    
+	  }
+	  embedding[ugraph.oppositeEdge(e)] = pn;
+
+	  pn = ugraph.oppositeEdge(ce), p = mine;	  
+	  e = embedding[ugraph.oppositeEdge(mine)];
+	  while (ugraph.target(e) != t) {
+	    typename UGraph::Edge n = 
+	      ugraph.direct(ugraph.addEdge(t, ugraph.source(e)), true);
+
+	    embedding[n] = pn;
+	    embedding[ugraph.oppositeEdge(n)] = e;
+	    embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
+
+	    pn = n;
+	    
+	    p = e;
+	    e = embedding[ugraph.oppositeEdge(e)];
+	    
+	  }
+	  embedding[ugraph.oppositeEdge(e)] = pn;
+	}
+      }
+    }
+
+  }
+
+  /// \brief Schnyder's planar drawing algorithms
+  ///
+  /// The planar drawing algorithm calculates location for each node
+  /// in the plane, which coordinates satisfies that if each edge is
+  /// represented with a straight line then the edges will not
+  /// intersect each other.
+  ///
+  /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
+  /// ie. each node will be located in the \c [0,n-2]x[0,n-2] square.
+  /// The time complexity of the algorithm is O(n).
+  template <typename UGraph>
+  class PlanarDrawing {
+  public:
+
+    UGRAPH_TYPEDEFS(typename UGraph);
+
+    /// \brief The point type for store coordinates
+    typedef dim2::Point<int> Point;
+    /// \brief The map type for store coordinates
+    typedef typename UGraph::template NodeMap<Point> PointMap;
+
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    /// \pre The ugraph should be simple, ie. loop and parallel edge free. 
+    PlanarDrawing(const UGraph& ugraph)
+      : _ugraph(ugraph), _point_map(ugraph) {}
+
+  private:
+
+    template <typename AuxUGraph, typename AuxEmbeddingMap>
+    void drawing(const AuxUGraph& ugraph, 
+		 const AuxEmbeddingMap& next, 
+		 PointMap& point_map) {
+      UGRAPH_TYPEDEFS(typename AuxUGraph);
+
+      typename AuxUGraph::template EdgeMap<Edge> prev(ugraph);
+
+      for (NodeIt n(ugraph); n != INVALID; ++n) {
+	Edge e = OutEdgeIt(ugraph, n);
+	
+	Edge p = e, l = e;
+	
+	e = next[e];
+	while (e != l) {
+	  prev[e] = p;
+	  p = e;
+	  e = next[e];
+	}
+	prev[e] = p;
+      }
+
+      Node anode, bnode, cnode;
+
+      {
+	Edge e = EdgeIt(ugraph);
+	anode = ugraph.source(e);
+	bnode = ugraph.target(e);
+	cnode = ugraph.target(next[ugraph.oppositeEdge(e)]);
+      }
+      
+      IterableBoolMap<AuxUGraph, Node> proper(ugraph, false);
+      typename AuxUGraph::template NodeMap<int> conn(ugraph, -1);
+
+      conn[anode] = conn[bnode] = -2;      
+      {
+	for (OutEdgeIt e(ugraph, anode); e != INVALID; ++e) {
+	  Node m = ugraph.target(e);
+	  if (conn[m] == -1) {
+	    conn[m] = 1;
+	  }
+	}
+	conn[cnode] = 2;
+
+	for (OutEdgeIt e(ugraph, bnode); e != INVALID; ++e) {
+	  Node m = ugraph.target(e);
+	  if (conn[m] == -1) {
+	    conn[m] = 1;
+	  } else if (conn[m] != -2) {
+	    conn[m] += 1;	    
+	    Edge pe = ugraph.oppositeEdge(e);
+	    if (conn[ugraph.target(next[pe])] == -2) {
+	      conn[m] -= 1;
+	    }
+	    if (conn[ugraph.target(prev[pe])] == -2) {
+	      conn[m] -= 1;
+	    }
+
+	    proper.set(m, conn[m] == 1);
+	  }
+	}
+      }
+      
+
+      typename AuxUGraph::template EdgeMap<int> angle(ugraph, -1);
+
+      while (proper.trueNum() != 0) {
+	Node n = typename IterableBoolMap<AuxUGraph, Node>::TrueIt(proper);
+	proper.set(n, false);
+	conn[n] = -2;
+
+	for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
+	  Node m = ugraph.target(e);
+	  if (conn[m] == -1) {
+	    conn[m] = 1;
+	  } else if (conn[m] != -2) {
+	    conn[m] += 1;	    
+	    Edge pe = ugraph.oppositeEdge(e);
+	    if (conn[ugraph.target(next[pe])] == -2) {
+	      conn[m] -= 1;
+	    }
+	    if (conn[ugraph.target(prev[pe])] == -2) {
+	      conn[m] -= 1;
+	    }
+
+	    proper.set(m, conn[m] == 1);
+	  }
+	}
+
+	{
+	  Edge e = OutEdgeIt(ugraph, n);
+	  Edge p = e, l = e;
+	  
+	  e = next[e];
+	  while (e != l) {
+	    
+	    if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) {
+	      Edge f = e;
+	      angle[f] = 0;
+	      f = next[ugraph.oppositeEdge(f)];
+	      angle[f] = 1;
+	      f = next[ugraph.oppositeEdge(f)];
+	      angle[f] = 2;
+	    }
+	    
+	    p = e;
+	    e = next[e];
+	  }
+	  
+	  if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) {
+	    Edge f = e;
+	    angle[f] = 0;
+	    f = next[ugraph.oppositeEdge(f)];
+	    angle[f] = 1;
+	    f = next[ugraph.oppositeEdge(f)];
+	    angle[f] = 2;
+	  }
+	}
+      }
+
+      typename AuxUGraph::template NodeMap<Node> apred(ugraph, INVALID);
+      typename AuxUGraph::template NodeMap<Node> bpred(ugraph, INVALID);
+      typename AuxUGraph::template NodeMap<Node> cpred(ugraph, INVALID);
+
+      typename AuxUGraph::template NodeMap<int> apredid(ugraph, -1);
+      typename AuxUGraph::template NodeMap<int> bpredid(ugraph, -1);
+      typename AuxUGraph::template NodeMap<int> cpredid(ugraph, -1);
+
+      for (EdgeIt e(ugraph); e != INVALID; ++e) {
+	if (angle[e] == angle[next[e]]) {
+	  switch (angle[e]) {
+	  case 2:
+	    apred[ugraph.target(e)] = ugraph.source(e);
+	    apredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
+	    break;
+	  case 1:
+	    bpred[ugraph.target(e)] = ugraph.source(e);
+	    bpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
+	    break;
+	  case 0:
+	    cpred[ugraph.target(e)] = ugraph.source(e);
+	    cpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
+	    break;
+	  }
+	}
+      }
+
+      cpred[anode] = INVALID;
+      cpred[bnode] = INVALID;
+
+      std::vector<Node> aorder, border, corder; 
+
+      {
+	typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
+	std::vector<Node> st;
+	for (NodeIt n(ugraph); n != INVALID; ++n) {
+	  if (!processed[n] && n != bnode && n != cnode) {
+	    st.push_back(n);
+	    processed[n] = true;
+	    Node m = apred[n];
+	    while (m != INVALID && !processed[m]) {
+	      st.push_back(m);
+	      processed[m] = true;
+	      m = apred[m];
+	    }
+	    while (!st.empty()) {
+	      aorder.push_back(st.back());
+	      st.pop_back();
+	    }
+	  }
+	}
+      }
+
+      {
+	typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
+	std::vector<Node> st;
+	for (NodeIt n(ugraph); n != INVALID; ++n) {
+	  if (!processed[n] && n != cnode && n != anode) {
+	    st.push_back(n);
+	    processed[n] = true;
+	    Node m = bpred[n];
+	    while (m != INVALID && !processed[m]) {
+	      st.push_back(m);
+	      processed[m] = true;
+	      m = bpred[m];
+	    }
+	    while (!st.empty()) {
+	      border.push_back(st.back());
+	      st.pop_back();
+	    }
+	  }
+	}
+      }
+
+      {
+	typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
+	std::vector<Node> st;
+	for (NodeIt n(ugraph); n != INVALID; ++n) {
+	  if (!processed[n] && n != anode && n != bnode) {
+	    st.push_back(n);
+	    processed[n] = true;
+	    Node m = cpred[n];
+	    while (m != INVALID && !processed[m]) {
+	      st.push_back(m);
+	      processed[m] = true;
+	      m = cpred[m];
+	    }
+	    while (!st.empty()) {
+	      corder.push_back(st.back());
+	      st.pop_back();
+	    }
+	  }
+	}
+      }
+
+      typename AuxUGraph::template NodeMap<int> atree(ugraph, 0);
+      for (int i = aorder.size() - 1; i >= 0; --i) {
+	Node n = aorder[i];
+	atree[n] = 1;
+	for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
+	  if (apred[ugraph.target(e)] == n) {
+	    atree[n] += atree[ugraph.target(e)];
+	  }
+	} 
+      }
+
+      typename AuxUGraph::template NodeMap<int> btree(ugraph, 0);
+      for (int i = border.size() - 1; i >= 0; --i) {
+	Node n = border[i];
+	btree[n] = 1;
+	for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
+	  if (bpred[ugraph.target(e)] == n) {
+	    btree[n] += btree[ugraph.target(e)];
+	  }
+	} 
+      }
+      
+      typename AuxUGraph::template NodeMap<int> apath(ugraph, 0);
+      apath[bnode] = apath[cnode] = 1;
+      typename AuxUGraph::template NodeMap<int> apath_btree(ugraph, 0);
+      apath_btree[bnode] = btree[bnode];
+      for (int i = 1; i < int(aorder.size()); ++i) {
+	Node n = aorder[i];
+	apath[n] = apath[apred[n]] + 1;
+	apath_btree[n] = btree[n] + apath_btree[apred[n]];
+      }
+
+      typename AuxUGraph::template NodeMap<int> bpath_atree(ugraph, 0);
+      bpath_atree[anode] = atree[anode];
+      for (int i = 1; i < int(border.size()); ++i) {
+	Node n = border[i];
+	bpath_atree[n] = atree[n] + bpath_atree[bpred[n]];
+      }
+
+      typename AuxUGraph::template NodeMap<int> cpath(ugraph, 0);
+      cpath[anode] = cpath[bnode] = 1;
+      typename AuxUGraph::template NodeMap<int> cpath_atree(ugraph, 0);
+      cpath_atree[anode] = atree[anode];
+      typename AuxUGraph::template NodeMap<int> cpath_btree(ugraph, 0);
+      cpath_btree[bnode] = btree[bnode];
+      for (int i = 1; i < int(corder.size()); ++i) {
+	Node n = corder[i];
+	cpath[n] = cpath[cpred[n]] + 1;
+	cpath_atree[n] = atree[n] + cpath_atree[cpred[n]];
+	cpath_btree[n] = btree[n] + cpath_btree[cpred[n]];
+      }
+
+      typename AuxUGraph::template NodeMap<int> third(ugraph);
+      for (NodeIt n(ugraph); n != INVALID; ++n) {
+	point_map[n].x = 
+	  bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1;
+	point_map[n].y = 
+	  cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1;
+      }
+      
+    }
+
+  public:
+
+    /// \brief Calculates the node locations
+    ///
+    /// This function calculates the node locations.
+    bool run() {
+      PlanarEmbedding<UGraph> pe(_ugraph);
+      if (!pe.run()) return false;
+      
+      run(pe);
+      return true;
+    }
+
+    /// \brief Calculates the node locations according to a
+    /// combinatorical embedding
+    ///
+    /// This function calculates the node locations. The \c embedding
+    /// parameter should contain a valid combinatorical embedding, ie.
+    /// a valid cyclic order of the edges.
+    template <typename EmbeddingMap>
+    void run(const EmbeddingMap& embedding) {
+      typedef SmartUEdgeSet<UGraph> AuxUGraph; 
+
+      if (3 * countNodes(_ugraph) - 6 == countUEdges(_ugraph)) {
+	drawing(_ugraph, embedding, _point_map);
+	return;
+      }
+
+      AuxUGraph aux_ugraph(_ugraph);
+      typename AuxUGraph::template EdgeMap<typename AuxUGraph::Edge> 
+	aux_embedding(aux_ugraph);
+
+      {
+
+	typename UGraph::template UEdgeMap<typename AuxUGraph::UEdge> 
+	  ref(_ugraph);
+	
+	for (UEdgeIt e(_ugraph); e != INVALID; ++e) {
+	  ref[e] = aux_ugraph.addEdge(_ugraph.source(e), _ugraph.target(e));
+	}
+
+	for (UEdgeIt e(_ugraph); e != INVALID; ++e) {
+	  Edge ee = embedding[_ugraph.direct(e, true)];
+	  aux_embedding[aux_ugraph.direct(ref[e], true)] = 
+	    aux_ugraph.direct(ref[ee], _ugraph.direction(ee));
+	  ee = embedding[_ugraph.direct(e, false)];
+	  aux_embedding[aux_ugraph.direct(ref[e], false)] = 
+	    aux_ugraph.direct(ref[ee], _ugraph.direction(ee));
+	}
+      }
+      _planarity_bits::makeConnected(aux_ugraph, aux_embedding);
+      _planarity_bits::makeBiNodeConnected(aux_ugraph, aux_embedding);
+      _planarity_bits::makeMaxPlanar(aux_ugraph, aux_embedding);
+      drawing(aux_ugraph, aux_embedding, _point_map);
+    }
+
+    /// \brief The coordinate of the given node
+    ///
+    /// The coordinate of the given node.
+    Point operator[](const Node& node) {
+      return _point_map[node];
+    }
+
+    /// \brief Returns the grid embedding in a \e NodeMap.
+    ///
+    /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
+    const PointMap& coords() const {
+      return _point_map;
+    }
+
+  private:
+    
+    const UGraph& _ugraph;
+    PointMap _point_map;
+    
+  };
+
 }
 
 #endif