LEDA Guide: Example Tutte Embedding

Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Graph Drawing Algorithms > Tutte Embedding > Example

Example Tutte Embedding

Let G=(V,E) be a graph without self loops. TUTTE_EMBEDDING() computes a Tutte Embedding of G in time O(|V|³).

The following program shows how TUTTE_EMBEDDING() can be used.

We first generate a graph G with 15 nodes and 26 edges by hand.

Then we define node_array<int> xpos, ypos for the x- and y- coordinates of the nodes.

Since the Tutte embedding wants to place the nodes in the center of gravity of its neighbors, some nodes need to get fixed positions beforehand. We add the first four nodes of G to the list<node> fixed_nodes and assign x- and y-coordinates.

Large Screenshot of Example

Using these parameters we call TUTTE_EMBEDDING(). The function returns false if it could not compute a Tutte Embedding and true otherwise.

We use GraphWin to visualize the result.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/node_array.h>
#include <LEDA/graph/graph_draw.h>
#include <LEDA/graphics/graphwin.h>

using namespace leda;

int main()
{
  graph G; 
  node n0=G.new_node();  node n1=G.new_node();
  node n2=G.new_node();  node n3=G.new_node();
  node n4=G.new_node();  node n5=G.new_node();
  node n6=G.new_node();  node n7=G.new_node();
  node n8=G.new_node();  node n9=G.new_node();
  node n10=G.new_node(); node n11=G.new_node();
  node n12=G.new_node(); node n13=G.new_node();
  node n14=G.new_node();

  G.new_edge(n0,n1);   G.new_edge(n1,n2);
  G.new_edge(n2,n3);   G.new_edge(n3,n4);
  G.new_edge(n4,n0);   G.new_edge(n5,n6);
  G.new_edge(n6,n7);
  G.new_edge(n7,n5);   G.new_edge(n0,n5);
  G.new_edge(n1,n6);   G.new_edge(n2,n7);
  G.new_edge(n8,n9);   G.new_edge(n9,n10);
  G.new_edge(n10,n11); G.new_edge(n11,n8);
  G.new_edge(n8,n3);   G.new_edge(n9,n4);
  G.new_edge(n10,n5);  G.new_edge(n11,n7);
  G.new_edge(n12,n13); G.new_edge(n13,n14);
  G.new_edge(n14,n12); G.new_edge(n13,n3);
  G.new_edge(n14,n1);  G.new_edge(n12,n8);
  G.new_edge(n13,n2);
  
  node_array<double> xpos(G), ypos(G);
  
  list<node> fixed_nodes;
  fixed_nodes.append(n0); fixed_nodes.append(n1);
  fixed_nodes.append(n2); fixed_nodes.append(n3);
  fixed_nodes.append(n4);
  xpos[n0]=100; ypos[n0]=50;
  xpos[n1]=400; ypos[n1]=50;
  xpos[n2]=450; ypos[n2]=250;
  xpos[n3]=250; ypos[n3]=400;
  xpos[n4]=50;  ypos[n4]=250;
  
  bool feasible=TUTTE_EMBEDDING(G,fixed_nodes,xpos,ypos);

  if (feasible) {
    GraphWin gw(G);
    gw.set_node_color(red);
    gw.set_position(xpos,ypos);
    gw.open(); gw.display();
  }
  
  return 0;
}

Example Tutte Embedding

See also: