Visualizing Directed Graphs

Yifan Hu

Wolfram Research, Inc.

Outline of this talk

What is a graph?

Why graph visualization?

What can Mathematica do?

How to draw directed graphs?

A few examples

Conclusions

What is a graph?

A graph consists of a set of vertices and a set of edges, G = {V, E}.

Graphs are often used to encapsulate relational information.

socialNetwork={"Li"->"Hu","Wang"->"Hu","Li"->"Wang","Carol"->"Andre","Carol"->"Fernando","Carol"->"Diane","Andre"->"Diane","Andre"->"Fernando","Andre"->"Beverly","Fernando"->"Diane","Fernando"->"Garth","Fernando"->"Heather","Diane"->"Beverly","Diane"->"Garth","Diane"->"Ed","Beverly"->"Garth","Beverly"->"Ed","Garth"->"Ed","Garth"->"Heather","Jane"->"Li","Jane"->"Hu","Heather"->"Ike","Ike"->"Jane","Li"->"Yang","Yang"->"Liu","Liu"->"Wang"};

Why Graph Visualization?

Visually appealing drawing of such graphs helps to understand complex relations, and discovery hidden pattern and knowledge.

Good graph drawing usually more helpful than a texture description

Many applications: social network, organizational chart, code analysis, bioinformatics.

A difficult problem: hard to find the best drawing manually other than for very small graphs.

An automatic procedure is thus useful.

What can Mathematica do?

Very efficient and high quality graph drawing algorithms are available in DiscreteMath`GraphPlot since Version 5.1.

<<DiscreteMath`GraphPlot`;
GraphPlot[{1->2,2->3,3->4,4->5,5->1}]

The key algorithm, using multilevel octree forced directed model, has complexity of O(|V| Log[|V|] + |E|).

What could Mathematica do: examples

Back to that social network: discover the structure

GraphPlot[g=socialNetwork,EdgeStyleFunction->({GrayLevel[.5], Line[{#1,#2}]}&),
VertexStyleFunction->({White,Disk[#,{0.07*StringLength[VertexList[g][[#]]],0.1}],GrayLevel[.5],Circle[#,{0.07*StringLength[VertexList[g][[#]]],0.1}],Blue,Text[VertexList[g][[#]],#]}&)]

What could Mathematica do: examples

Some small graphs

data

Clear[x];
x=Table[1,{100}];
g={1->2,2->3,3->4,4->5,5->6,6->7,7->8,8->9,9->1,10->1,10->2,10->3,10->4,10->5,10->6,10->7,10->8,10->9,11->9,11->1,12->1,12->2,13->2,13->3,14->3,14->4,15->4,15->5,16->5,16->6,17->6,17->7,18->7,18->8,19->8,19->9,10->11,10->12,10->13,10->14,10->15,10->16,10->17,10->18,10->19};
x[[1]]=GraphPlot[g,PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];
g={1->1,1->2,1->9,1->8,2->2,2->3,2->10,3->3,3->4,3->11,4->4,4->12,4->5,5->5,5->6,5->13,6->6,6->7,6->14,7->7,7->8,7->15,8->8,8->16,9->9,9->10,9->16,9->17,10->10,10->11,10->18,11->11,11->12,11->19,12->12,12->13,12->20,13->13,13->14,13->21,14->14,14->15,14->22,15->15,15->16,15->23,16->16,16->24,17->17,17->18,17->24,18->18,18->19,19->19,19->20,20->20,20->21,21->21,21->22,22->22,22->23,23->23,23->24};
x[[2]]=GraphPlot[g,PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];
x[[3]]=GraphPlot[g={1->2,1->4,1->6,1->8,1->10,1->12,2->3,2->4,3->14,3->20,3->25,4->5,4->6,5->15,5->20,5->21,6->7,6->8,7->16,7->21,7->22,8->9,8->10,9->17,9->22,9->23,10->11,10->12,11->18,11->23,11->24,12->13,12->2,13->19,13->24,13->25,14->20,15->21,16->22,17->23,18->24,19->25,20->15,21->16,22->17,23->18,24->19,25->14},PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];
x[[4]]=GraphPlot[g={1->2,1->3,2->13,2->19,2->24,3->4,3->5,4->14,4->19,4->20,5->6,5->7,6->15,6->20,6->21,7->8,7->9,8->16,8->21,8->22,9->10,9->11,10->17,10->22,10->23,11->12,11->1,12->18,12->23,12->24,13->19,14->20,15->21,16->22,17->23,18->24,19->14,20->15,21->16,22->17,23->18,24->13},PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];
g={1->2,1->3,1->4,1->5,1->6,1->7,1->8,1->9,2->3,2->10,3->4,3->11,4->5,4->12,5->6,5->13,6->7,6->14,7->8,7->15,8->9,8->16,9->2,9->17,10->18,11->26,12->34,13->42,14->50,15->58,16->66,17->74,18->19,19->20,19->32,20->21,21->22,22->23,23->24,24->25,25->10,26->27,27->28,27->40,28->29,29->30,30->31,31->32,32->33,33->11,34->35,35->36,35->48,36->37,37->38,38->39,39->40,40->41,41->12,42->43,43->44,43->56,44->45,45->46,46->47,47->48,48->49,49->13,50->51,51->52,51->64,52->53,53->54,54->55,55->56,56->57,57->14,58->59,59->60,59->72,60->61,61->62,62->63,63->64,64->65,65->15,66->67,67->68,67->80,68->69,69->70,70->71,71->72,72->73,73->16,74->75,75->76,75->24,76->77,77->78,78->79,79->80,80->81,81->17};
x[[5]]=GraphPlot[g,PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),Method->SpringModel,DisplayFunction->Identity];
x[[6]]=GraphPlot[g,PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),Method->SpringElectricalModel,DisplayFunction->Identity];
g={1->2,1->9,2->3,2->10,3->4,3->11,4->5,4->12,5->6,5->13,6->7,6->14,7->8,7->15,8->1,8->16,9->17,10->25,11->33,12->41,13->49,14->57,15->65,16->73,17->18,18->19,18->31,18->23,19->20,20->21,21->22,22->23,23->24,24->9,25->26,26->27,26->39,26->31,27->28,28->29,29->30,30->31,31->32,32->10,33->34,34->35,34->47,34->39,35->36,36->37,37->38,38->39,39->40,40->11,41->42,42->43,42->55,42->47,43->44,44->45,45->46,46->47,47->48,48->12,49->50,50->51,50->63,50->55,51->52,52->53,53->54,54->55,55->56,56->13,57->58,58->59,58->71,58->63,59->60,60->61,61->62,62->63,63->64,64->14,65->66,66->67,66->79,66->71,67->68,68->69,69->70,70->71,71->72,72->15,73->74,74->75,74->23,74->79,75->76,76->77,77->78,78->79,79->80,80->16};
x[[7]]=GraphPlot[g,PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),Method->SpringElectricalModel,DisplayFunction->Identity];
g={1->2,1->6,2->3,3->4,4->5,4->11,4->12,5->13,5->14,6->5,6->15,7->2,8->2,9->3,10->3,10->21,11->22,11->23,12->24,12->23,13->26,13->25,14->27,14->26,15->28,16->6,16->30,16->29,17->1,18->1,19->9,20->9,20->10,22->45,23->46,23->47,24->48,25->49,26->50,27->52,28->56,29->15,29->55,31->18,32->17,32->18,33->17,34->7,35->7,35->8,36->8,37->35,37->40,37->63,38->34,38->37,38->64,39->36,39->41,39->61,40->35,40->39,40->62,41->19,41->42,42->20,42->43,42->83,43->20,43->44,44->21,44->45,44->81,45->46,46->47,46->79,47->48,48->77,49->48,50->49,51->26,51->50,52->51,53->30,53->54,54->29,54->55,54->69,55->56,56->52,57->33,57->53,57->67,58->32,58->57,59->32,59->58,59->65,60->31,60->38,60->59,60->66,61->62,61->91,64->63,65->66,66->94,67->68,68->58,69->70,70->53,71->56,71->72,71->100,72->55,73->51,73->74,74->52,75->50,75->76,76->49,76->85,77->78,78->47,79->80,80->45,80->88,81->82,81->90,82->43,83->84,84->41,85->86,86->87,87->77,88->89,89->90,91->92,92->93,93->84,94->95,95->96,96->64,97->70,98->97,99->98,99->67,100->101,101->102,102->74,114->103,103->104,104->105,105->106,106->107,107->108,109->108,110->109,111->110,112->111,113->112,114->113,2->103,105->3,107->4,109->5,111->6,1->113};
x[[8]]=GraphPlot[g,PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),Method->SpringElectricalModel,DisplayFunction->Identity];
x[[9]]=GraphPlot[{1->2,1->6,1->113,2->3,2->103,3->4,4->5,4->11,4->12,5->13,5->14,6->5,6->15,7->2,8->2,9->3,10->3,10->21,11->22,11->23,12->24,12->23,13->26,13->25,14->27,14->26,15->28,16->6,16->30,16->29,17->1,18->1,19->9,20->9,20->10,22->45,23->46,23->47,24->48,25->49,26->50,27->52,28->56,29->15,29->55,31->18,32->17,32->18,33->17,34->7,35->7,35->8,36->8,37->35,37->40,37->63,38->34,38->37,38->64,39->36,39->41,39->61,39->117,40->35,40->39,40->62,41->19,41->42,42->20,42->43,42->83,43->20,43->44,44->21,44->45,44->81,44->118,45->46,45->118,46->47,46->79,47->48,48->77,49->48,49->119,50->49,51->26,51->50,52->51,53->30,53->54,54->29,54->55,54->69,55->56,56->52,57->33,57->53,57->67,58->32,58->57,59->32,59->58,59->65,60->31,60->38,60->59,60->66,61->62,61->91,64->63,65->66,66->94,67->68,68->58,69->70,70->53,71->56,71->72,71->100,72->55,73->51,73->74,74->52,75->50,75->76,76->49,76->85,77->78,78->47,79->80,80->45,80->88,81->82,81->90,82->43,83->84,84->41,85->86,85->119,86->87,87->77,88->89,89->90,91->92,92->93,93->84,94->95,94->116,95->96,96->64,97->70,97->121,98->97,99->98,99->67,99->121,100->101,100->120,101->102,102->74,102->120,103->104,104->105,105->106,105->3,106->107,107->108,107->4,108->115,109->108,109->5,110->109,110->115,111->110,111->6,112->111,113->112,114->103,114->113,115->112,115->114,115->106,115->104,116->96,116->60,116->38,117->91,117->93,117->41,118->88,118->90,119->48,119->87,120->56,120->52,121->53,121->57,51->122,122->26,122->50,55->123,123->29,123->54,58->124,124->59,32->124,125->37,35->125,125->40,126->42,20->126,126->43,127->23,47->127,127->46},PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];
x[[10]]=GraphPlot[{1->2,1->6,2->3,3->4,4->5,4->11,4->12,5->13,5->14,6->5,6->15,7->2,8->2,9->3,10->3,10->21,11->22,11->23,12->24,12->23,13->26,13->25,14->27,14->26,15->28,16->6,16->30,16->29,17->1,18->1,19->9,20->9,20->10,22->45,23->46,23->47,24->48,25->49,26->50,27->52,28->56,29->15,29->55,31->18,32->17,32->18,33->17,34->7,35->7,35->8,36->8,37->35,37->40,38->34,38->37,39->36,39->41,40->35,40->39,41->19,41->42,42->20,42->43,43->20,43->44,44->21,44->45,45->46,46->47,47->48,49->48,50->49,51->26,51->50,52->51,53->30,53->54,54->29,54->55,55->56,56->52,57->33,57->53,58->32,58->57,59->32,59->58,60->31,60->38,60->59,51->27,27->26,50->25,26->25,24->47,24->23,46->22,23->22,21->43,21->20,42->19,20->19,36->40,36->35,34->35,34->37,33->32,32->31,59->31,33->58,28->29,28->55,29->30,54->30,56->15,53->16,57->17,18->60,38->7,8->39,9->41,10->44,11->45,48->12,13->49,52->14},Method->SpringModel,PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];
x[[11]]=GraphPlot[{1->2,1->6,2->3,3->4,4->5,4->11,4->12,5->13,5->14,6->5,6->15,7->2,8->2,9->3,10->3,10->21,11->22,11->23,12->24,12->23,13->26,13->25,14->27,14->26,15->28,16->6,16->30,16->29,17->1,18->1,19->9,20->9,20->10,22->45,23->46,23->47,24->48,25->49,26->50,27->52,28->56,29->15,29->55,31->18,32->17,32->18,33->17,34->7,35->7,35->8,36->8,37->35,37->40,38->34,38->37,39->36,39->41,40->35,40->39,41->19,41->42,42->20,42->43,43->20,43->44,44->21,44->45,45->46,46->47,47->48,49->48,50->49,51->26,51->50,52->51,53->30,53->54,54->29,54->55,55->56,56->52,57->33,57->53,58->32,58->57,59->32,59->58,60->31,60->38,60->59,51->27,27->26,50->25,26->25,24->47,24->23,46->22,23->22,21->43,21->20,42->19,20->19,36->40,36->35,34->35,34->37,33->32,32->31,59->31,33->58,28->29,28->55,29->30,54->30,56->15,53->16,57->17,18->60,38->7,8->39,9->41,10->44,11->45,48->12,13->49,52->14},Method->SpringModel,PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];
g={1->2,2->3,3->4,4->5,5->6,6->7,7->8,8->9,9->10,10->10,10->11,11->12,12->13,13->14,15->16,16->17,17->18,18->1,14->19,13->19,19->12,12->20,11->20,20->10,10->21,21->9,9->9,21->8,8->22,22->7,22->6,6->23,23->4,23->5,4->24,24->3,24->2,2->25,25->1,25->18,18->26,26->17,16->26,16->27,15->27,14->15,14->27,9->7,7->23,23->24,1->24,17->1,15->17,13->15,13->20,20->9};
x[[12]]=GraphPlot[g,Method->SpringModel,PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];
x[[13]]=GraphPlot[g,PlotStyle->{PointSize[0.03]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];
g={1->2,1->24,2->3,2->25,3->4,4->5,4->24,5->6,6->7,6->23,7->8,7->23,8->9,8->22,9->10,9->9,9->7,10->10,10->11,10->21,11->12,11->20,12->13,12->20,13->14,13->19,13->15,13->20,14->19,14->15,14->27,15->16,15->27,15->17,16->17,16->26,16->27,17->18,17->1,18->1,18->26,19->12,20->10,20->9,21->9,21->8,22->7,22->6,23->4,23->5,23->24,24->3,24->2,25->1,25->18,26->17,28->29,28->51,29->30,29->52,30->31,31->32,31->51,32->33,33->34,33->50,34->35,34->50,35->36,35->49,36->37,36->36,36->34,37->37,37->38,37->48,38->39,38->47,39->40,39->47,40->41,40->46,40->42,40->47,41->46,41->42,41->54,42->43,42->54,42->44,43->44,43->53,43->54,44->45,44->28,45->28,45->53,46->39,47->37,47->36,48->36,48->35,49->34,49->33,50->31,50->32,50->51,51->30,51->29,52->28,52->45,53->44,55->56,55->78,56->57,56->79,57->58,58->59,58->78,59->60,60->61,60->77,61->62,61->77,62->63,62->76,63->64,63->63,63->61,64->64,64->65,64->75,65->66,65->74,66->67,66->74,67->68,67->73,67->69,67->74,68->73,68->69,68->81,69->70,69->81,69->71,70->71,70->80,70->81,71->72,71->55,72->55,72->80,73->66,74->64,74->63,75->63,75->62,76->61,76->60,77->58,77->59,77->78,78->57,78->56,79->55,79->72,80->71,82->83,82->105,83->84,83->106,84->85,85->86,85->105,86->87,87->88,87->104,88->89,88->104,89->90,89->103,90->91,90->90,90->88,91->91,91->92,91->102,92->93,92->101,93->94,93->101,94->95,94->100,94->96,94->101,95->100,95->96,95->108,96->97,96->108,96->98,97->98,97->107,97->108,98->99,98->82,99->82,99->107,100->93,101->91,101->90,102->90,102->89,103->88,103->87,104->85,104->86,104->105,105->84,105->83,106->82,106->99,107->98,109->110,109->132,110->111,110->133,111->112,112->113,112->132,113->114,114->115,114->131,115->116,115->131,116->117,116->130,117->118,117->117,117->115,118->118,118->119,118->129,119->120,119->128,120->121,120->128,121->122,121->127,121->123,121->128,122->127,122->123,122->135,123->124,123->135,123->125,124->125,124->134,124->135,125->126,125->109,126->109,126->134,127->120,128->118,128->117,129->117,129->116,130->115,130->114,131->112,131->113,131->132,132->111,132->110,133->109,133->126,134->125,136->137,136->159,137->138,137->160,138->139,139->140,139->159,140->141,141->142,141->158,142->143,142->158,143->144,143->157,144->145,144->144,144->142,145->145,145->146,145->156,146->147,146->155,147->148,147->155,148->149,148->154,148->150,148->155,149->154,149->150,149->162,150->151,150->162,150->152,151->152,151->161,151->162,152->153,152->136,153->136,153->161,154->147,155->145,155->144,156->144,156->143,157->142,157->141,158->139,158->140,158->159,159->138,159->137,160->136,160->153,161->152,161->119,134->92,107->26,11->53,38->80,66->146};
x[[14]]=GraphPlot[g,Method->SpringModel,PlotStyle->{PointSize[0.02]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];
x[[15]]=GraphPlot[g,PlotStyle->{PointSize[0.02]},VertexStyleFunction->({Blue,Point[#]}&),DisplayFunction->Identity];

g=Show[GraphicsArray[Partition[Table[x[[i]],{i,15}],{5}]],DisplayFunction->$DisplayFunction];
Clear[x];
g

What can Mathematica do: examples

An example using data from a sparse matrix collection

lock3491 (Cross-cone vehicle structure)

g =Import["lock3491.pse","HarwellBoeing"];
ArrayPlot[g,FrameTicks->All, MaxPlotPoints->300]

This graph has many components, all but two are non trivial. We sort the components according to size

cs=StrongComponents[g];
cs=Sort[cs,Length[#1]>Length[#2]&];
Map[Length,cs]//Short

The first component

gc=g[[cs[[1]],cs[[1]]]];
t=Timing[
gr=GraphPlot[gc,VertexStyleFunction->({}&),EdgeStyleFunction->Automatic];];
Print["size = ",Dimensions[gc][[1]]," edges = ",Round[Length[gc@NonzeroPositions[]]/2]," CPU time = ",t[[1]]];
gr

The second component

gc=g[[cs[[2]],cs[[2]]]];
t=Timing[
gr=GraphPlot3D[gc,VertexStyleFunction->({}&),EdgeStyleFunction->Automatic];];
Print["size = ",Dimensions[gc][[1]]," edges = ",Round[Length[gc@NonzeroPositions[]]/2]," CPU time = ",t[[1]]];
gr

What can Mathematica do: examples

Trees

TreePlot[RandomTree[200]]

What about directed graphs?

A food chain example

foodchain ={Racoon->Bird, Racoon->Insect, Wildcat->Bird, Wildcat->Rodent, Fox->Bird, Fox->Gartersnake, Fox->Salamander, Fox->Rabbit, Fox->Rodent, Wolf->Rabbit, Wolf->Rodent, Wolf->Skunk, Wolf->Deer, Bear->Deer, Bear->Rodent, Bear->Plant, Bird->Plant, Gartersnake->Insect, Gartersnake->Toad,Salamander->Insect, Rabbit->Plant,Skunk->Rodent, Skunk->Insect, Deer->Plant, Toad->Insect, Insect->Plant};

What about directed graphs?

Using an algorithm designed for undirected graph is not so satisfactory

GraphPlot[g=foodchain,EdgeStyleFunction->(Arrow[{#1,#2},.1]&),
VertexStyleFunction->({White,Disk[#,{.04*StringLength[ToString[VertexList[g][[#]]]],.12}],
Black,Circle[#,{.04*StringLength[ToString[VertexList[g][[#]]]],.12}],Black,Text[VertexList[g][[#]],#]}&)]

How to draw directed graphs?

The algorithm implemented for DAGs (Directed Acyclic Graphs) follows the algorithm of Sugiyama et al. (K. Sugiyama, S. Tagawa and M. Toda, Methods for visual understanding of hierarchical systems, IEEE Trans. Syst. Man Cybern., SMC-11, No. 2, PP. 109-125, 1981), and subsequence development (e.g., the DOT software).

It consists of a number of stages:

1. Vertices of the DAG is first assigned a preliminary y ranking such that if there is an edge from i to j, then it is likely that yrank(i)>yrank(j).This is to ensure that the final drawing has directed edges pointing mostly downwards, and to break cycles.

How to draw directed graphs? Step 2.

2. The y coordinates are generated so if there is an edge from i to j and yrank(i)> yrank(j), their y coordinates are as close as possible, but separated by a set minimum. This is so that the final resulting drawing does not have many long edges. This assigns the vertices into a finite number of layers. If an edge lies across a number of layers, virtual vertices are added.

Min (∑_( {i,j}∈ E, rank[i] > rank[j])) y[i] - y[j]
s.t. y[i]-y[j]≥1, for all {i, j}∈E such that rank[i] > rank[j]

Solved using linear programming

Example: {1 -> 2, 2 -> 3, 1 -> 3}

Min (y[1]-y[2])+(y[1]-y[3])+(y[2]-y[3])
s.t. y[1]-y[2]≥ 1, y[1]-y[3]≥1, y[2]-y[3]≥1

Minimize[{(y[1]-y[2])+(y[1]-y[3])+(y[2]-y[3]),y[1]-y[2]≥1&&y[1]-y[3]≥1&&y[2]-y[3]≥1},{y[1],y[2],y[3]}]

Developer`SetSystemOptions["GraphPlotOptions"->{"NumberBezierSplinePoints"->1}];
res=DirectedGraphPlot[g={1->2,2->3,1->3},
EdgeStyleFunction->(Arrow[#,.17]&),
VertexStyleFunction->({White,Disk[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.15}],
Black,Circle[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.15}],Black,Text[VertexList[g][[#]],#]}&)];
Developer`SetSystemOptions["GraphPlotOptions"->{"NumberBezierSplinePoints"->10}];
res

3. Virtual vertices are added (see later). A preliminary x ranking is assigned to each vertex to minimize the number of edge crossing

For example, this layout has three crossovers, after swapping 3 and 6, there will be no crossovers

Manipulate[GraphPlot[g={1->2,2->3,1->4,1->5,2->6,1->7,7->3,1->8,8->6},
VertexCoordinates->{{0.`,2.`},{1.`,1.`},{x,0.`},{-2.`,1.`},{-1.`,1.`},{1-x,0.`},{0.`,1.`},{4.`,1.`}},
EdgeStyleFunction->(Arrow[{#1,#2},.15]&),
VertexStyleFunction->({White,Disk[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.15}],
Black,Circle[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.15}],Black,Text[VertexList[g][[#]],#]}&)],{{x,2},0,2}]

4. The x coordinates are generated by minimize (∑_(i-> j)) | x(i) - x(j)|, subject to the constraints that vertices on the same layer obey the x ranking generated in Step 3, and are separated by a set minimum, again using linear programming

Minimize  |x[1]-x[4]| +|x[1]-x[5]|+|x[1]-x[7]|+|[x[1]-x[2]|+|x[1]-x[8]|+
                          |x[7]-x[3]|+|x[2]-x[3]|+|x[2]-x[6]|+|x[8]-x[6]|
subject to      x[5]-x[4]>1,x[7]-x[5]>1,x[2]-x[7]>1,x[8]-x[2]>1,x[6]-x[3]>1

Converted to a LP problem

FindMinimum[
{z14+z15+z17+z12+z18+z73+z23+z26+z86,{x[5]-x[4]>1,x[7]-x[5]>1,x[2]-x[7]>1,x[8]-x[2]>1,x[6]-x[3]>1,
z14>x[1]-x[4],z14>x[4]-x[1],
z15>x[1]-x[5],z15>x[5]-x[1],
z17>x[1]-x[7],z17>x[7]-x[1],
z12>x[1]-x[2],z12>x[2]-x[1],
z18>x[1]-x[8],z18>x[8]-x[1],
z73>x[7]-x[3],z73>x[3]-x[7],
z23>x[2]-x[3],z23>x[3]-x[2],
z26>x[2]-x[6],z26>x[6]-x[2],
z86>x[8]-x[6],z86>x[6]-x[8]
}},{x[1],x[2],x[3],x[4],x[5],x[6],x[7],x[8],z14,z15,z17,z12,z18,z73,z23,z26,z86}]

NMinimize[{Abs[x[1]-x[4]]+Abs[x[1]-x[5]]+Abs[x[1]-x[7]]+Abs[x[1]-x[2]]+Abs[x[1]-x[8]]+Abs[x[7]-x[3]]+Abs[x[2]-x[3]]+Abs[x[2]-x[6]]+Abs[x[8]-x[6]],
{x[4]==1,x[5]-x[4]>1,x[7]-x[5]>1,x[2]-x[7]>1,x[8]-x[2]>1,x[6]-x[3]>1}},{x[1],x[2],x[3],x[4],x[5],x[6],x[7],x[8]}]//Timing

5. Multiline edges are replaced with Bezier spline to be more visually appealing

Manipulate[
Developer`SetSystemOptions["GraphPlotOptions"->{"NumberBezierSplinePoints"->Ceiling[n]}];
g1=DirectedGraphPlot[g={1->2,2->3,1->3,1->4,1->5,2->6,1->6},
EdgeStyleFunction->(Arrow[#,.15]&),
VertexStyleFunction->({White,Disk[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.15}],
Black,Circle[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.15}],Black,Text[VertexList[g][[#]],#]}&),ImageSize->700];Developer`SetSystemOptions["GraphPlotOptions"->{"NumberBezierSplinePoints"->10}];
g1,{n,1,9}]

Developer`SetSystemOptions["GraphPlotOptions"->{"NumberBezierSplinePoints"->1}];
g1=DirectedGraphPlot[g={1->2,2->3,1->3,1->4,1->5,2->6,1->6},
EdgeStyleFunction->(Arrow[#,.15]&),
VertexStyleFunction->({White,Disk[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.15}],
Black,Circle[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.15}],Black,Text[VertexList[g][[#]],#]}&)];Developer`SetSystemOptions["GraphPlotOptions"->{"NumberBezierSplinePoints"->10}];
g2=DirectedGraphPlot[g={1->2,2->3,1->3,1->4,1->5,2->6,1->6},
EdgeStyleFunction->(Arrow[#,.15]&),
VertexStyleFunction->({White,Disk[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.15}],
Black,Circle[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.15}],Black,Text[VertexList[g][[#]],#]}&)];
GraphicsArray[{g1,g2}]

A flow chart example with multiedges and loops

g={total->TotalDispatch,TotalList->CheckThreading,TotalList->TotalDispatch,TotalSparse->TotalDispatch,TotalSparse->TotalDispatch,TotalDispatch->TotalDispatch,TotalDispatch->TotalList,TotalDispatch->TotalPacked,TotalDispatch->TotalSparse};
width = 0.02; height = 0.06;
DirectedGraphPlot[g,
EdgeStyleFunction->(Arrow[#,.06]&),
VertexStyleFunction->({White,Disk[#,{width*StringLength[ToString[VertexList[g][[#]]]],height}],
Black,Circle[#,{width*StringLength[ToString[VertexList[g][[#]]]],height}],Black,Text[VertexList[g][[#]],#]}&)]

An evolution history of Unix

DirectedGraphPlot[g={"5th Edition"->"6th Edition","5th Edition"->"PWB 1.0","6th Edition"->"1 BSD","6th Edition"->"Interdata","6th Edition"->"LSX","6th Edition"->"Mini Unix","6th Edition"->"Wollongong","PWB 1.0"->"PWB 1.2","PWB 1.0"->"USG 1.0","1 BSD"->"2 BSD","Interdata"->"PWB 2.0","Interdata"->"Unix/TS 3.0","Interdata"->"7th Edition", "PWB 1.2"->"PWB 2.0","USG 1.0"->"USG 2.0","USG 1.0"->"CB Unix 1","7th Edition"->"2 BSD","7th Edition"->"32V","7th Edition"->"Xenix","7th Edition"->"Ultrix-11","7th Edition"->"UniPlus+","7th Edition"->"V7M","PWB 2.0"->"Unix/TS 3.0","USG 2.0"->"USG 3.0","CB Unix 1"->"CB Unix 2","32V"->"3 BSD","Unix/TS 1.0"->"Unix/TS 3.0","USG 3.0"->"Unix/TS 3.0","CB Unix 2"->"CB Unix 3","3 BSD"->"4 BSD","V7M"->"Ultrix-11","Unix/TS 3.0"->"TS 4.0","CB Unix 3"->"Unix/TS++","CB Unix 3"->"PDP-11 Sys V","4 BSD"->"4.1 BSD","Unix/TS++"->"TS 4.0","4.1 BSD"->"8th Edition","4.1 BSD"->"4.2 BSD","4.1 BSD"->"2.8 BSD","2 BSD"->"2.8 BSD", "TS 4.0"->"System V.0","4.2 BSD"->"4.3 BSD","4.2 BSD"->"Ultrix-32","2.8 BSD"->"2.9 BSD","2.8 BSD"->"Ultrix-11","System V.0"->"System V.2","8th Edition"->"9th Edition","System V.2"->"System V.3"},EdgeStyleFunction->(Arrow[#,.1]&),
VertexStyleFunction->({White,Disk[#,{.06*StringLength[ToString[VertexList[g][[#]]]],.15}],
Black,Circle[#,{.06*StringLength[ToString[VertexList[g][[#]]]],.15}],Black,Text[VertexList[g][[#]],#]}&)]

Another example

g={S8->9,S24->27,S24->25,S1->10,S1->2,S35->36,S35->43,S30->31,S30->33,9->42,9->T1,25->T1,25->26,27->T24,2->3,2->16,2->17,2->T1,2->18,10->11,10->14,10->T1,10->13,10->12,31->T1,31->32,33->T30,33->34,42->4,26->4,3->4,16->15,17->19,18->29,11->4,14->15,37->39,37->41,37->38,37->40,13->19,12->29,43->38,43->40,36->19,32->23,34->29,39->15,41->29,38->4,40->19,4->5,19->21,19->20,19->28,5->6,5->T35,5->23,21->22,20->15,28->29,6->7,15->T1,22->23,22->T35,29->T30,7->T8,23->T24,23->T1};
DirectedGraphPlot[g,EdgeStyleFunction->(Arrow[#,.05]&),
VertexStyleFunction->({White,Disk[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.2}],
Black,Circle[#,{.15*StringLength[ToString[VertexList[g][[#]]]],.2}],Black,Text[VertexList[g][[#]],#]}&)]

A flow chart example of NSum.

g={ratiotest->ratiolimit,getdata->dir_inf_bad,getdata->evalderiv,NSPpreliminaries->getdata,findsp->termlimit,findsp->ratiotest,findsp->nSumW,findsp->nSumEM,findsp->nProductEM,findsp->nProductW,nSumW->nSumFinite,nSumW->nSumWtail,nSumEM->evalterm,nSumEM->nSumFinite,nSumEM->evalderiv,nProductEM->nPFinite,nProductW->nPFinite,nProductW->nPWtail,oNSum->CleanOptionList,oNSum->multidim,oNSum->NSPpreliminaries,oNSum->findsp,nSumFinite->evalterm,nSumWtail->evalterm,nSumWtail->epsalg,oNProduct->CleanOptionList,oNProduct->multidim,oNProduct->NSPpreliminaries,oNProduct->findsp,nPFinite->evalterm,nPWtail->evalterm,nPWtail->epsalg,oSequenceLimit->epsalg};
width = 0.04; height = 0.15;
DirectedGraphPlot[g,EdgeStyleFunction->(Arrow[#,.1]&),
VertexStyleFunction->({White,Disk[#,{width*StringLength[ToString[VertexList[g][[#]]]],height}],
Black,Circle[#,{width*StringLength[ToString[VertexList[g][[#]]]],height}],Black,Text[VertexList[g][[#]],#]}&)]

A flow chart example for a large code

DirectedGraphPlot[g={"start"->"main","start"->"on_exit","main"->"sort","main"->"merge","main"->"term","main"->"signal","main"->"sbrk","main"->"unlink","main"->"newfile","main"->"fclose","main"->"close","main"->"brk","main"->"setbuf","main"->"copyproto","main"->"initree","main"->"safeoutfil","main"->"getpid","main"->"sprintf","main"->"creat","main"->"rem","main"->"oldfile","sort"->"msort","sort"->"filbuf","sort"->"newfile","sort"->"fclose","sort"->"setbuf","sort"->"setfil","msort"->"qsort","msort"->"insert","sort"->"wline","msort"->"div","msort"->"cmpsave","merge"->"insert","merge"->"rline","erge"->"wline","merge"->"unlink","merge"->"fopen","merge"->"fclose","merge"->"setfil","merge"->"mul","merge"->"setbuf","merge"->"cmpsave","insert"->"cmpa","wline"->"flsbuf","qsort"->"cmpa","rline"->"filbuf","xflsbuf"->"write","flsbuf"->"xflsbuf","filbuf"->"read","term"->"unlink","term"->"signal","term"->"setfil","term"->"exit","endopen"->"open","fopen"->"endopen","fopen"->"findiop","newfile"->"fopen","newfile"->"setfil","fclose"->"fflush","fclose"->"close","fflush"->"xflsbuf","malloc"->"morecore","malloc"->"demote","morecore"->"sbrk","morecore"->"getfreehdr","morecore"->"free","morecore"->"getpagesize","morecore"->"putfreehdr","morecore"->"udiv","morecore"->"umul","on_exit"->"malloc","signal"->"sigvec","getfreehdr"->"sbrk","free"->"insert","insert"->"getfreehdr","setfil"->"div","setfil"->"rem","sigvec"->"sigblock","sigvec"->"sigsetmask","doprnt"->"urem","doprnt"->"udiv","doprnt"->"strlen","doprnt"->"localeconv","sprintf"->"doprnt"},EdgeStyleFunction->(Arrow[#,.15]&),
VertexStyleFunction->({{White,Disk[#1,{StringLength[VertexList[g][[#1]]]*0.04,.3}]},Circle[#1,{StringLength[VertexList[g][[#1]]]*0.04,.3}],Text[VertexList[g][[#1]],#1]}&),AspectRatio->1.,Rotation->-90]

Finally, let's apply the algorithm to the foodchain example

DirectedGraphPlot[g=foodchain,
EdgeStyleFunction->(Arrow[#,.1]&),
VertexStyleFunction->({White,Disk[#,{.06*StringLength[ToString[VertexList[g][[#]]]],.15}],
Black,Circle[#,{.06*StringLength[ToString[VertexList[g][[#]]]],.15}],Black,Text[VertexList[g][[#]],#]}&)]

And making it more fun

g=foodchain;
coord=GraphCoordinates[g,Method->LayeredDigraphDrawing];
names = VertexList[g];
pics[Rabbit]=Import["rabbit.gif"][[1]];
pics[Fox]=Import["fox.jpg"][[1]];
pics[Skunk]=Import["skunk.gif"][[1]];
pics[Plant]=Import["Plant.gif"][[1]];
pics[Wolf]=Import["wolf.gif"][[1]];
pics[Deer]=Import["deer.gif"][[1]];
pics[Bear]=Import["bear.jpg"][[1]];
pics[Rodent]=Import["rodent.gif"][[1]];
pics[Toad]=Import["toad.gif"][[1]];
pics[Gartersnake]=Import["snake.jpg"][[1]];
pics[Wildcat]=Import["cat.gif"][[1]];
pics[Insect]=Import["insect.gif"][[1]];
pics[Salamander]=Import["salamander.jpg"][[1]];
pics[Racoon]=Import["raccoon.gif"][[1]];
pics[Bird]=Import["bird.gif"][[1]];
reposition[Raster[x_,y_,z___],pos_]:= Raster[x,pos,z];
reposition[x_,y__]:=x;
DirectedGraphPlot[g,EdgeStyleFunction->(Arrow[#3,.3]&),
VertexStyleFunction->(
reposition[pics[names[[#]]],{coord[[#]]-.3,coord[[#]]+.3}]
&)]

Conclusions

Mathematica has highly efficient and high quality graph drawing algorithms for undirected graph (since Version 5.1).

In a future release, it will also have an efficient and high quality undirected graph drawing algorithm.

Further possible improvement include better support to interaction between arrow and node shapes/graphics.

It would be interesting to combine this capability with other features of Mathematica, e.g., with the profiler/debugger.

Initialization

SetDirectory["/home/yifanhu/RD_HTML/Yifan_Hu/TALKS/Technology_2005/DIRECTED_GRAPH"];
<<DiscreteMath`GraphPlot`;
DirectedGraphPlot[g_,opts___?OptionQ]:=Module[{gr},
gr= GraphPlot[g,opts,PlotStyle->(Arrowheads[.02]),Method->LayeredDigraphDrawing];
gr
];

Manipulate[GraphPlot[Table[i->Mod[Random[Integer,{0,n}],n],{i,0,n-1}],VertexStyleFunction->({}&)],{n,100,200}]

Manipulate[GraphPlot[Table[i->Mod[Random[Integer,{0,n}],n],{i,0,n-1}],VertexStyleFunction->({}&),Method->LayeredDigraphDrawing],{n,10,40}]