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|2). 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;
}

See also:

Straight Line Embedding

Node Arrays

GraphWin

Graph Drawing Algorithms

Algorithms for Planar Graphs

Planar Maps

Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Graph Drawing Algorithms