LEDA Guide: Example Straight Line Embedding

> LEDA Guide > Graph Algorithms > Graph Drawing Algorithms > Straight Line Embedding > Example

Example Straight Line Embedding

Let G=(V,E) be a planar graph without self loops and parallel edges. STRAIGHTLINE_EMBEDDING() computes a straight line embedding of G in time O(|V|²).

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

We first generate a random planar graph G with 10 nodes and 20 edges.

Then we define node_array<int> xcoord, ycoord for the x- and y- coordinates of the nodes and call STRAIGHTLINE_EMBEDDING().

We use GraphWin to visualize the result. To do this we need to transform the integer coordinates into appropriate GraphWin coordinates.

Large Screenshot of Example

#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; 
  random_planar_graph(G,10,20);
 
  node_array<int> xcoord(G);
  node_array<int> ycoord(G);
  
  int max_coord=STRAIGHT_LINE_EMBEDDING(G,xcoord,ycoord);
  
  std::cout << "maximal coordinate in drawing is "
            << max_coord << std::endl;

  GraphWin gw(G);
  gw.set_node_color(red); //nodes are drwan red

  //transform coordinates of nodes
  node_array<point> pos(G);node v;
  forall_nodes(v,G) {
    pos[v]=point(25*xcoord[v]+50,40*ycoord[v]+100);
  }  
  gw.set_layout(pos);   //tell GraphWin the node coordinates

  gw.open(); gw.display();  //open and display GraphWin
  
  return 0;
}

Example Straight Line Embedding

See also: