%% -------------------------------------------------------------------
%%      Algorithms for Drawing Graphs: an Annotated Bibliography
%% 
%%        Giuseppe Di Battista       dibattista@iasi.rm.cnr.it
%%                 Peter Eades       eades@cs.newcastle.edu.au
%%            Roberto Tamassia       rt@cs.brown.edu
%%           Ioannis G. Tollis       tollis@utdallas.edu
%%
%%                         LaTeX document
%%
%% -------------------------------------------------------------------
\newif\ifesp \espfalse		% CGTA reprint
\newif\iffig \figtrue		% figures
%% -------------------------------------------------------------------

\ifesp		\documentstyle{espart}

\else 		\documentstyle{article}

\title{ Algorithms for Drawing Graphs: \\ an Annotated Bibliography%
%
\thanks{This document is available via anonymous {\tt ftp} from {\tt
wilma.cs.brown.edu (128.148.33.66)}, files {\tt
/pub/papers/compgeo/gdbiblio.tex.Z} and {\tt
/pub/papers/compgeo/gdbiblio.ps.Z}.}
}

\author{
Giuseppe Di Battista \\
Dipartimento di Informatica e Sistemistica \\
Universit\`a di Roma ``La Sapienza'' \\
Via Salaria, 113 --- Roma \\
00198 Italy \\
{\tt dibattista@iasi.rm.cnr.it}
\and
Peter Eades \\
Department of Computer Science \\
University of Newcastle \\
University Drive --- Callaghan \\
NSW 2308, Australia \\
{\tt eades@cs.newcastle.edu.au}
\and
Roberto Tamassia \\
Department of Computer Science \\
Brown University \\
Providence, RI 02912--1910 \\
USA \\
{\tt rt@cs.brown.edu}
\and
Ioannis G.\ Tollis \\
Department of Computer Science \\
The University of Texas at Dallas \\
Richardson, Texas 75083--0688 \\
USA \\
{\tt tollis@utdallas.edu}
}

\date{June 1994}

\fi
 
%% -------------------------------------------------------------------

\iffig 

\newcommand{\poly}
{
\begin{picture}(341,181) 
\put(175.25,170.25){\circle*{10}} 
\put(155.25,150.25){\circle*{10}} 
\put(235.25,150.25){\circle*{10}} 
\put(175,170){\line(-1,-1){20}} 
\put(175,170){\line(3,-1){60}} 
\put(175,170){\line(-3,-1){60}} 
\put(155.25,90.25){\circle*{10}} 
\put(155,150){\line(-2,-3){20}} 
\put(135,120){\line(2,-3){20}} 
\put(195.25,120.25){\circle*{10}} 
\put(155,90){\line(4,3){80}} 
\put(155,150){\line(4,-3){40}} 
\put(185.25,50.25){\circle*{10}} 
\put(155,90){\line(3,-4){30}} 
\put(195,120){\line(0,-1){45}} 
\put(195,75){\line(-2,-5){10}} 
\put(185.25,10.25){\circle*{10}} 
\put(195,120){\line(2,-3){20}} 
\put(215,90){\line(0,-1){35}} 
\put(235.25,35.25){\circle*{10}} 
\put(235,150){\line(0,-1){115}} 
\put(115,150){\line(0,-1){105}} 
\put(185,10){\line(-2,1){70}} 
\put(185,10){\line(2,1){50}} 
\put(185,10){\line(2,3){30}} 
\put(185,50){\line(0,-1){40}} 
\end{picture} 
}

\newcommand{\straight}
{
\begin{picture}(341,141) 
\put(110.25,130.25){\circle*{10}} 
\put(110,130){\line(1,0){100}} 
\put(210.25,130.25){\circle*{10}} 
\put(270.25,110.25){\circle*{10}} 
\put(210,130){\line(3,-1){60}} 
\put(270.25,10.25){\circle*{10}} 
\put(270,110){\line(0,-1){100}} 
\put(210,130){\line(1,-5){20}} 
\put(230,30){\line(2,-1){40}} 
\put(230.25,30.25){\circle*{10}} 
\put(170.25,30.25){\circle*{10}} 
\put(170,30){\line(5,4){100}} 
\put(170,30){\line(1,0){60}} 
\put(155.25,85.25){\circle*{10}} 
\put(110,130){\line(1,-1){45}} 
\put(85.25,50.25){\circle*{10}} 
\put(155,85){\line(-2,-1){70}} 
\put(85,50){\line(4,-1){80}} 
\end{picture} 
}

\newcommand{\ortho}
{
\begin{picture}(341,176) 
\put(75.25,115.25){\circle*{10}} 
\put(75,115){\line(0,1){50}} 
\put(75.25,165.25){\circle*{10}} 
\put(75,165){\line(1,0){160}} 
\put(235.25,165.25){\circle*{10}} 
\put(235,165){\line(0,-1){25}} 
\put(235,140){\line(1,0){40}} 
\put(275.25,140.25){\circle*{10}} 
\put(275,140){\line(0,-1){20}} 
\put(275.25,120.25){\circle*{10}} 
\put(235,45){\framebox(40,75){}} 
\put(275.25,45.25){\circle*{10}} 
\put(235.25,45.25){\circle*{10}} 
\put(75,115){\line(0,-1){110}} 
\put(235,5){\line(0,1){40}} 
\put(75,115){\line(1,0){85}} 
\put(160,115){\line(0,-1){35}} 
\put(160,80){\line(1,0){35}} 
\put(195,80){\line(0,1){60}} 
\put(195,140){\line(-1,0){85}} 
\put(110,140){\line(0,-1){95}} 
\put(110,45){\line(1,0){125}} 
\put(110.25,140.25){\circle*{10}} 
\put(160.25,80.25){\circle*{10}} 
\put(110.25,45.25){\circle*{10}} 
\put(75,5){\line(1,0){160}} 
\end{picture} 
}

\newcommand{\cube}
{
\begin{picture}(341,111) 
\put(185.25,80.25){\circle*{10}} 
\put(245.25,80.25){\circle*{10}} 
\put(185,80){\line(2,1){40}} 
\put(225,100){\line(1,0){60}} 
\put(245,80){\line(2,1){40}} 
\put(185,80){\line(0,-1){60}} 
\put(225.25,100.25){\circle*{10}} 
\put(185,80){\line(1,0){60}} 
\put(285.25,100.25){\circle*{10}} 
\put(185.25,20.25){\circle*{10}} 
\put(185,20){\line(1,0){60}} 
\put(245,80){\line(0,-1){60}} 
\put(225,100){\line(0,-1){60}} 
\put(225,40){\line(1,0){60}} 
\put(285,100){\line(0,-1){60}} 
\put(185,20){\line(2,1){40}} 
\put(245,20){\line(2,1){40}} 
\put(225.25,40.25){\circle*{10}} 
\put(245.25,20.25){\circle*{10}} 
\put(285.25,40.25){\circle*{10}} 
\put(70,30){\framebox(50,50){}} 
\put(50,10){\framebox(90,90){}} 
\put(50,10){\line(1,1){20}} 
\put(50,100){\line(1,-1){20}} 
\put(120,80){\line(1,1){20}} 
\put(120,30){\line(1,-1){20}} 
\put(70.25,80.25){\circle*{10}} 
\put(50.25,100.25){\circle*{10}} 
\put(140.25,100.25){\circle*{10}} 
\put(120.25,80.25){\circle*{10}} 
\put(70.25,30.25){\circle*{10}} 
\put(50.25,10.25){\circle*{10}} 
\put(120.25,30.25){\circle*{10}} 
\put(140.25,10.25){\circle*{10}} 
\end{picture} 
}

\newcommand{\tree}
{
\begin{picture}(341,211) 
\put(140,195){\line(-3,-4){30}} 
\put(140,195){\line(3,-4){30}} 
\put(110,155){\line(0,-1){40}} 
\put(110,155){\line(-1,-1){40}} 
\put(170,155){\line(1,-2){20}} 
\put(190,115){\line(-1,-4){10}} 
\put(190,115){\line(3,-4){30}} 
\put(140.25,195.25){\circle*{10}} 
\put(110.25,155.25){\circle*{10}} 
\put(70.25,115.25){\circle*{10}} 
\put(110.25,115.25){\circle*{10}} 
\put(150.25,115.25){\circle*{10}} 
\put(170.25,155.25){\circle*{10}} 
\put(190.25,115.25){\circle*{10}} 
\put(180.25,75.25){\circle*{10}} 
\put(220.25,75.25){\circle*{10}} 
\put(80,25){\vector(1,0){140}} 
\put(125,5){\makebox(40,15)[t]{width}} 
\put(240,190){\makebox(50,15)[t]{Level 0}} 
\put(240,150){\makebox(50,15)[t]{Level 1}} 
\put(240,110){\makebox(50,15)[t]{Level 2}} 
\put(240,70){\makebox(50,15)[t]{Level 3}} 
\put(60,75){\line(1,0){10}} 
\put(80,75){\line(1,0){10}} 
\put(100,75){\line(1,0){10}} 
\put(120,75){\line(1,0){10}} 
\put(140,75){\line(1,0){10}} 
\put(160,75){\line(1,0){10}} 
\put(180,75){\line(1,0){10}} 
\put(200,75){\line(1,0){10}} 
\put(220,75){\line(1,0){10}} 
\put(60,115){\line(1,0){10}} 
\put(80,115){\line(1,0){10}} 
\put(100,115){\line(1,0){10}} 
\put(120,115){\line(1,0){10}} 
\put(140,115){\line(1,0){10}} 
\put(160,115){\line(1,0){10}} 
\put(180,115){\line(1,0){10}} 
\put(200,115){\line(1,0){10}} 
\put(220,115){\line(1,0){10}} 
\put(60,155){\line(1,0){10}} 
\put(80,155){\line(1,0){10}} 
\put(100,155){\line(1,0){10}} 
\put(120,155){\line(1,0){10}} 
\put(140,155){\line(1,0){10}} 
\put(160,155){\line(1,0){10}} 
\put(180,155){\line(1,0){10}} 
\put(200,155){\line(1,0){10}} 
\put(220,155){\line(1,0){10}} 
\put(60,195){\line(1,0){10}} 
\put(80,195){\line(1,0){10}} 
\put(100,195){\line(1,0){10}} 
\put(120,195){\line(1,0){10}} 
\put(140,195){\line(1,0){10}} 
\put(160,195){\line(1,0){10}} 
\put(180,195){\line(1,0){10}} 
\put(200,195){\line(1,0){10}} 
\put(220,195){\line(1,0){10}} 
\put(150,115){\line(-1,1){40}} 
\put(180,60){\vector(1,0){40}} 
\put(180,45){\makebox(110,15)[l]{minimum horizontal}} 
\put(180,35){\makebox(70,15)[l]{separation}} 
\put(205,60){\vector(-1,0){25}} 
\put(190,25){\vector(-1,0){120}} 
\end{picture} 
}

\newcommand{\convex}
{
\begin{picture}(341,201) 
\put(180.25,190.25){\circle*{10}} 
\put(180,190){\line(-2,-3){40}} 
\put(140,130){\line(2,-3){20}} 
\put(180,190){\line(2,-3){40}} 
\put(220,130){\line(-2,-3){20}} 
\put(160,100){\line(1,0){40}} 
\put(160,100){\line(-2,-3){20}} 
\put(140,70){\line(2,-3){40}} 
\put(200,100){\line(2,-3){20}} 
\put(220,70){\line(-2,-3){40}} 
\put(140,130){\line(-3,1){60}} 
\put(180,190){\line(-5,-2){100}} 
\put(140,70){\line(-3,-1){60}} 
\put(80,150){\line(0,-1){100}} 
\put(80,50){\line(5,-2){100}} 
\put(180,190){\line(5,-2){100}} 
\put(220,130){\line(3,1){60}} 
\put(280,150){\line(0,-1){100}} 
\put(220,70){\line(3,-1){60}} 
\put(180,10){\line(5,2){100}} 
\put(80.25,150.25){\circle*{10}} 
\put(80.25,50.25){\circle*{10}} 
\put(140.25,130.25){\circle*{10}} 
\put(160.25,100.25){\circle*{10}} 
\put(140.25,70.25){\circle*{10}} 
\put(200.25,100.25){\circle*{10}} 
\put(220.25,130.25){\circle*{10}} 
\put(280.25,150.25){\circle*{10}} 
\put(220.25,70.25){\circle*{10}} 
\put(180.25,10.25){\circle*{10}} 
\put(280.25,50.25){\circle*{10}} 
\end{picture} 
}

\newcommand{\areabend}
{
\begin{picture}(341,196) 
\put(50.25,140.25){\circle*{10}} 
\put(80,110){\framebox(60,60){}} 
\put(260.25,80.25){\circle*{10}} 
\put(20,140){\line(1,0){60}} 
\put(50,140){\line(0,-1){60}} 
\put(50,80){\line(1,0){90}} 
\put(140,110){\line(0,-1){30}} 
\put(20,140){\line(0,-1){90}} 
\put(20,50){\line(1,0){150}} 
\put(140,140){\line(1,0){30}} 
\put(170,140){\line(0,-1){90}} 
\put(80.25,170.25){\circle*{10}} 
\put(110.25,170.25){\circle*{10}} 
\put(140.25,170.25){\circle*{10}} 
\put(80.25,140.25){\circle*{10}} 
\put(140.25,140.25){\circle*{10}} 
\put(140.25,110.25){\circle*{10}} 
\put(140.25,80.25){\circle*{10}} 
\put(100,175){\makebox(20,15)[t]{1}} 
\put(130,175){\makebox(20,15)[t]{2}} 
\put(140,140){\makebox(20,15)[t]{3}} 
\put(70,175){\makebox(20,15)[t]{4}} 
\put(60,145){\makebox(20,15)[t]{5}} 
\put(30,145){\makebox(20,15)[t]{6}} 
\put(140,60){\makebox(20,15)[t]{7}} 
\put(140,95){\makebox(20,15)[t]{8}} 
\put(230,50){\framebox(90,90){}} 
\put(260,50){\framebox(60,60){}} 
\put(260,50){\framebox(30,30){}} 
\put(230.25,140.25){\circle*{10}} 
\put(230.25,50.25){\circle*{10}} 
\put(260.25,50.25){\circle*{10}} 
\put(290.25,50.25){\circle*{10}} 
\put(290.25,80.25){\circle*{10}} 
\put(320.25,140.25){\circle*{10}} 
\put(320.25,110.25){\circle*{10}} 
\put(215,145){\makebox(20,15)[t]{1}} 
\put(300,145){\makebox(20,15)[t]{2}} 
\put(300,110){\makebox(20,15)[t]{3}} 
\put(220,25){\makebox(20,15)[t]{4}} 
\put(250,25){\makebox(20,15)[t]{5}} 
\put(240,80){\makebox(20,15)[t]{6}} 
\put(290,80){\makebox(20,15)[t]{7}} 
\put(280,25){\makebox(20,15)[t]{8}} 
\put(190,50){\line(1,0){5}} 
\put(200,50){\line(1,0){5}} 
\put(210,50){\line(1,0){5}} 
\put(220,50){\line(1,0){5}} 
\put(320,50){\line(1,0){5}} 
\put(330,50){\line(1,0){5}} 
\put(10,80){\line(1,0){5}} 
\put(20,80){\line(1,0){5}} 
\put(30,80){\line(1,0){5}} 
\put(40,80){\line(1,0){5}} 
\put(10,110){\line(1,0){5}} 
\put(20,110){\line(1,0){5}} 
\put(30,110){\line(1,0){5}} 
\put(40,110){\line(1,0){5}} 
\put(50,110){\line(1,0){5}} 
\put(330,80){\line(1,0){5}} 
\put(320,140){\line(1,0){5}} 
\put(330,140){\line(1,0){5}} 
\put(300,80){\line(1,0){5}} 
\put(310,80){\line(1,0){5}} 
\put(320,80){\line(1,0){5}} 
\put(60,110){\line(1,0){5}} 
\put(70,110){\line(1,0){5}} 
\put(10,140){\line(1,0){5}} 
\put(10,50){\line(1,0){5}} 
\put(170,50){\line(1,0){5}} 
\put(180,50){\line(1,0){5}} 
\put(180,80){\line(1,0){5}} 
\put(190,80){\line(1,0){5}} 
\put(200,80){\line(1,0){5}} 
\put(210,80){\line(1,0){5}} 
\put(220,80){\line(1,0){5}} 
\put(230,80){\line(1,0){5}} 
\put(240,80){\line(1,0){5}} 
\put(250,80){\line(1,0){5}} 
\put(260,80){\line(1,0){5}} 
\put(180,140){\line(1,0){5}} 
\put(190,140){\line(1,0){5}} 
\put(200,140){\line(1,0){5}} 
\put(320,110){\line(1,0){5}} 
\put(330,110){\line(1,0){5}} 
\put(150,80){\line(1,0){5}} 
\put(160,80){\line(1,0){5}} 
\put(170,80){\line(1,0){5}} 
\put(190,170){\line(1,0){5}} 
\put(200,170){\line(1,0){5}} 
\put(210,170){\line(1,0){5}} 
\put(220,170){\line(1,0){5}} 
\put(230,170){\line(1,0){5}} 
\put(240,170){\line(1,0){5}} 
\put(250,170){\line(1,0){5}} 
\put(260,170){\line(1,0){5}} 
\put(270,170){\line(1,0){5}} 
\put(280,170){\line(1,0){5}} 
\put(290,170){\line(1,0){5}} 
\put(300,170){\line(1,0){5}} 
\put(310,170){\line(1,0){5}} 
\put(320,170){\line(1,0){5}} 
\put(330,170){\line(1,0){5}} 
\put(150,170){\line(1,0){5}} 
\put(160,170){\line(1,0){5}} 
\put(170,170){\line(1,0){5}} 
\put(180,170){\line(1,0){5}} 
\put(190,110){\line(1,0){5}} 
\put(200,110){\line(1,0){5}} 
\put(210,110){\line(1,0){5}} 
\put(220,110){\line(1,0){5}} 
\put(230,110){\line(1,0){5}} 
\put(240,110){\line(1,0){5}} 
\put(250,110){\line(1,0){5}} 
\put(150,110){\line(1,0){5}} 
\put(160,110){\line(1,0){5}} 
\put(170,110){\line(1,0){5}} 
\put(180,110){\line(1,0){5}} 
\put(80,140){\line(1,0){5}} 
\put(90,140){\line(1,0){5}} 
\put(100,140){\line(1,0){5}} 
\put(110,140){\line(1,0){5}} 
\put(120,140){\line(1,0){5}} 
\put(130,140){\line(1,0){5}} 
\put(210,140){\line(1,0){5}} 
\put(220,140){\line(1,0){5}} 
\put(170,140){\line(1,0){5}} 
\put(10,170){\line(1,0){5}} 
\put(20,170){\line(1,0){5}} 
\put(30,170){\line(1,0){5}} 
\put(40,170){\line(1,0){5}} 
\put(50,170){\line(1,0){5}} 
\put(60,170){\line(1,0){5}} 
\put(50,75){\line(0,-1){5}} 
\put(50,65){\line(0,-1){5}} 
\put(50,55){\line(0,-1){5}} 
\put(80,105){\line(0,-1){5}} 
\put(140,75){\line(0,-1){5}} 
\put(140,65){\line(0,-1){5}} 
\put(140,55){\line(0,-1){5}} 
\put(80,65){\line(0,-1){5}} 
\put(80,55){\line(0,-1){5}} 
\put(80,95){\line(0,-1){5}} 
\put(80,85){\line(0,-1){5}} 
\put(80,75){\line(0,-1){5}} 
\put(50,165){\line(0,-1){5}} 
\put(50,155){\line(0,-1){5}} 
\put(110,65){\line(0,-1){5}} 
\put(110,55){\line(0,-1){5}} 
\put(110,95){\line(0,-1){5}} 
\put(110,85){\line(0,-1){5}} 
\put(110,75){\line(0,-1){5}} 
\put(110,115){\line(0,-1){5}} 
\put(110,105){\line(0,-1){5}} 
\put(110,145){\line(0,-1){5}} 
\put(110,135){\line(0,-1){5}} 
\put(110,125){\line(0,-1){5}} 
\put(50,145){\line(0,-1){5}} 
\put(170,165){\line(0,-1){5}} 
\put(170,155){\line(0,-1){5}} 
\put(170,145){\line(0,-1){5}} 
\put(290,105){\line(0,-1){5}} 
\put(290,95){\line(0,-1){5}} 
\put(200,155){\line(0,-1){5}} 
\put(200,145){\line(0,-1){5}} 
\put(200,135){\line(0,-1){5}} 
\put(200,125){\line(0,-1){5}} 
\put(200,115){\line(0,-1){5}} 
\put(200,105){\line(0,-1){5}} 
\put(200,95){\line(0,-1){5}} 
\put(200,85){\line(0,-1){5}} 
\put(200,75){\line(0,-1){5}} 
\put(200,65){\line(0,-1){5}} 
\put(200,55){\line(0,-1){5}} 
\put(110,155){\line(0,-1){5}} 
\put(110,165){\line(0,-1){5}} 
\put(20,165){\line(0,-1){5}} 
\put(20,155){\line(0,-1){5}} 
\put(20,145){\line(0,-1){5}} 
\put(260,165){\line(0,-1){5}} 
\put(260,155){\line(0,-1){5}} 
\put(290,145){\line(0,-1){5}} 
\put(290,135){\line(0,-1){5}} 
\put(290,125){\line(0,-1){5}} 
\put(290,115){\line(0,-1){5}} 
\put(260,145){\line(0,-1){5}} 
\put(260,135){\line(0,-1){5}} 
\put(260,125){\line(0,-1){5}} 
\put(260,115){\line(0,-1){5}} 
\put(320,165){\line(0,-1){5}} 
\put(320,155){\line(0,-1){5}} 
\put(200,165){\line(0,-1){5}} 
\put(290,165){\line(0,-1){5}} 
\put(290,155){\line(0,-1){5}} 
\put(230,165){\line(0,-1){5}} 
\put(230,155){\line(0,-1){5}} 
\put(55,5){\makebox(100,15)[t]{area 20, bends 6}} 
\put(225,5){\makebox(100,15)[t]{area 9, bends 2}} 
\end{picture} 
}

\newcommand{\visibility}
{
\begin{picture}(341,186) 
\put(40,165){\line(1,0){280}} 
\put(40,125){\line(1,0){40}} 
\put(40,85){\line(1,0){40}} 
\put(40,45){\line(1,0){40}} 
\put(40,5){\line(1,0){280}} 
\put(120,45){\line(1,0){80}} 
\put(240,45){\line(1,0){80}} 
\put(160,125){\line(1,0){120}} 
\put(60,165){\line(0,-1){160}} 
\put(140,165){\line(0,-1){120}} 
\put(160,45){\line(0,-1){40}} 
\put(180,125){\line(0,-1){80}} 
\put(260,125){\line(0,-1){80}} 
\put(280,45){\line(0,-1){40}} 
\put(300,165){\line(0,-1){120}} 
\put(60,85){\makebox(20,15)[t]{1}} 
\put(60,125){\makebox(20,15)[t]{2}} 
\put(180,165){\makebox(20,15)[t]{3}} 
\put(60,45){\makebox(20,15)[t]{4}} 
\put(180,5){\makebox(20,15)[t]{5}} 
\put(155,45){\makebox(20,15)[t]{6}} 
\put(205,125){\makebox(20,15)[t]{7}} 
\put(270,45){\makebox(20,15)[t]{8}} 
\end{picture} 
}

\newcommand{\tessellation}
{
\begin{picture}(341,276) 
\put(70.25,265.25){\circle*{10}} 
\put(70,265){\line(-1,-1){40}} 
\put(30.25,225.25){\circle*{10}} 
\put(110.25,225.25){\circle*{10}} 
\put(70,265){\line(1,-1){40}} 
\put(70.25,205.25){\circle*{10}} 
\put(30,225){\line(2,-1){40}} 
\put(110,225){\line(-2,-1){40}} 
\put(90.25,165.25){\circle*{10}} 
\put(130.25,185.25){\circle*{10}} 
\put(70,205){\line(1,-2){20}} 
\put(110,225){\line(1,-2){20}} 
\put(130,185){\line(-2,-1){40}} 
\put(130,185){\line(-2,-3){40}} 
\put(90.25,125.25){\circle*{10}} 
\put(90,165){\line(0,-1){40}} 
\put(30,225){\line(3,-5){60}} 
\put(25,160){\makebox(50,15)[]{$e_1$}} 
\put(60,145){\makebox(50,15)[]{$e_2$}} 
\put(100,145){\makebox(50,15)[]{$e_3$}} 
\put(45,180){\makebox(50,15)[]{$e_4$}} 
\put(80,175){\makebox(50,15)[]{$e_5$}} 
\put(30,215){\makebox(50,15)[]{$e_6$}} 
\put(60,215){\makebox(50,15)[]{$e_7$}} 
\put(100,200){\makebox(50,15)[]{$e_8$}} 
\put(20,245){\makebox(50,15)[]{$e_9$}} 
\put(75,240){\makebox(60,20)[]{$e_{10}$}} 
\put(140,5){\framebox(150,120){}} 
\put(145,95){\line(1,0){50}} 
\put(170,90){\line(0,-1){80}} 
\put(260,10){\line(0,1){50}} 
\put(200,125){\line(0,-1){55}} 
\put(175,35){\line(1,0){80}} 
\put(175,65){\line(1,0){50}} 
\put(205,95){\line(1,0){80}} 
\put(230,40){\line(0,1){50}} 
\put(235,65){\line(1,0){50}} 
\put(130,45){\makebox(50,15)[]{$e_1$}} 
\put(190,10){\makebox(50,15)[]{$e_2$}} 
\put(250,30){\makebox(50,15)[]{$e_3$}} 
\put(175,40){\makebox(50,15)[]{$e_4$}} 
\put(220,40){\makebox(50,15)[]{$e_5$}} 
\put(160,70){\makebox(50,15)[]{$e_6$}} 
\put(190,70){\makebox(50,15)[]{$e_7$}} 
\put(235,70){\makebox(50,15)[]{$e_8$}} 
\put(145,100){\makebox(50,15)[]{$e_9$}} 
\put(215,100){\makebox(60,20)[]{$e_{10}$}} 
\put(145,220){\makebox(30,15)[t]{(a)}} 
\put(100,35){\makebox(30,15)[t]{(b)}} 
\end{picture} 
}

\newcommand{\upward}
{
\begin{picture}(341,206) 
\put(140.25,10.25){\circle*{10}} 
\put(140,10){\vector(-1,1){45}} 
\put(140,10){\vector(2,1){60}} 
\put(90.25,60.25){\circle*{10}} 
\put(205.25,45.25){\circle*{10}} 
\put(90,60){\vector(3,2){45}} 
\put(205,45){\vector(-4,3){60}} 
\put(140.25,95.25){\circle*{10}} 
\put(140,95){\vector(-1,1){45}} 
\put(90,60){\vector(0,1){75}} 
\put(90.25,140.25){\circle*{10}} 
\put(205,45){\vector(1,2){45}} 
\put(250.25,140.25){\circle*{10}} 
\put(140,95){\vector(3,4){75}} 
\put(250,140){\vector(-1,2){25}} 
\put(220.25,195.25){\circle*{10}} 
\put(140,95){\vector(-1,3){25}} 
\put(90,140){\vector(2,3){20}} 
\put(110.25,175.25){\circle*{10}} 
\end{picture} 
}

\newcommand{\hierarchy}
{
\begin{picture}(341,156) 
\put(80.25,10.25){\circle*{10}} 
\put(80,10){\vector(1,2){20}} 
\put(105.25,55.25){\circle*{10}} 
\put(130,10){\vector(-1,2){20}} 
\put(130.25,10.25){\circle*{10}} 
\put(130,10){\vector(1,2){20}} 
\put(155.25,55.25){\circle*{10}} 
\put(180,10){\vector(-1,2){20}} 
\put(180.25,10.25){\circle*{10}} 
\put(130.25,100.25){\circle*{10}} 
\put(105,55){\vector(1,2){20}} 
\put(130,10){\vector(0,1){85}} 
\put(105,55){\vector(3,2){60}} 
\put(170.25,100.25){\circle*{10}} 
\put(205.25,55.25){\circle*{10}} 
\put(205,55){\vector(-3,4){30}} 
\put(200.25,100.25){\circle*{10}} 
\put(180,10){\vector(1,4){20}} 
\put(75.25,145.25){\circle*{10}} 
\put(105,50){\vector(-1,3){30}} 
\put(105.25,145.25){\circle*{10}} 
\put(170.25,145.25){\circle*{10}} 
\put(215.25,145.25){\circle*{10}} 
\put(130,100){\vector(-1,2){20}} 
\put(200.25,145.25){\circle*{10}} 
\put(170,100){\vector(0,1){40}} 
\put(200,100){\vector(0,1){40}} 
\put(50,10){\line(1,0){10}} 
\put(70,10){\line(1,0){10}} 
\put(90,10){\line(1,0){10}} 
\put(110,10){\line(1,0){10}} 
\put(130,10){\line(1,0){10}} 
\put(150,10){\line(1,0){10}} 
\put(170,10){\line(1,0){10}} 
\put(190,10){\line(1,0){10}} 
\put(210,10){\line(1,0){10}} 
\put(230,10){\line(1,0){10}} 
\put(50,55){\line(1,0){10}} 
\put(70,55){\line(1,0){10}} 
\put(90,55){\line(1,0){10}} 
\put(110,55){\line(1,0){10}} 
\put(130,55){\line(1,0){10}} 
\put(150,55){\line(1,0){10}} 
\put(170,55){\line(1,0){10}} 
\put(190,55){\line(1,0){10}} 
\put(210,55){\line(1,0){10}} 
\put(230,55){\line(1,0){10}} 
\put(50,100){\line(1,0){10}} 
\put(70,100){\line(1,0){10}} 
\put(90,100){\line(1,0){10}} 
\put(110,100){\line(1,0){10}} 
\put(130,100){\line(1,0){10}} 
\put(150,100){\line(1,0){10}} 
\put(170,100){\line(1,0){10}} 
\put(190,100){\line(1,0){10}} 
\put(210,100){\line(1,0){10}} 
\put(230,100){\line(1,0){10}} 
\put(50,145){\line(1,0){10}} 
\put(70,145){\line(1,0){10}} 
\put(90,145){\line(1,0){10}} 
\put(110,145){\line(1,0){10}} 
\put(130,145){\line(1,0){10}} 
\put(150,145){\line(1,0){10}} 
\put(170,145){\line(1,0){10}} 
\put(190,145){\line(1,0){10}} 
\put(210,145){\line(1,0){10}} 
\put(230,145){\line(1,0){10}} 
\put(155,55){\vector(3,4){60}} 
\end{picture} 
}

\newcommand{\hstrategy}
{
\begin{picture}(341,301) 
\put(205.25,40.25){\circle*{10}} 
\put(205,40){\vector(1,1){35}} 
\put(245.25,80.25){\circle*{10}} 
\put(285.25,40.25){\circle*{10}} 
\put(285,40){\vector(-1,1){35}} 
\put(205.25,120.25){\circle*{10}} 
\put(285.25,120.25){\circle*{10}} 
\put(265.25,80.25){\circle*{10}} 
\put(285,40){\vector(-1,2){15}} 
\put(205,40){\vector(0,1){75}} 
\put(285,40){\vector(0,1){75}} 
\put(245,80){\vector(1,1){35}} 
\put(245.25,120.25){\circle*{10}} 
\put(205,40){\vector(1,2){35}} 
\put(245,80){\vector(0,1){30}} 
\put(305.25,80.25){\circle*{10}} 
\put(285,40){\vector(1,2){15}} 
\put(210,30){\makebox(20,20)[]{1}} 
\put(290,30){\makebox(20,20)[]{2}} 
\put(310,80){\makebox(20,20)[]{3}} 
\put(225,70){\makebox(20,20)[]{4}} 
\put(265,70){\makebox(20,20)[]{5}} 
\put(250,110){\makebox(20,20)[]{6}} 
\put(210,110){\makebox(20,20)[]{7}} 
\put(290,110){\makebox(20,20)[]{8}} 
\put(35.25,40.25){\circle*{10}} 
\put(75.25,80.25){\circle*{10}} 
\put(115.25,40.25){\circle*{10}} 
\put(115.25,80.25){\circle*{10}} 
\put(135.25,80.25){\circle*{10}} 
\put(35,40){\line(0,1){40}} 
\put(35,40){\line(1,2){20}} 
\put(55.25,120.25){\circle*{10}} 
\put(35,80){\vector(1,2){15}} 
\put(95.25,120.25){\circle*{10}} 
\put(55,80){\vector(1,1){35}} 
\put(75,80){\vector(1,2){15}} 
\put(35,40){\vector(1,1){35}} 
\put(115,40){\vector(-1,1){35}} 
\put(115,40){\vector(0,1){35}} 
\put(115,40){\vector(2,3){20}} 
\put(115.25,120.25){\circle*{10}} 
\put(115,40){\line(1,1){40}} 
\put(75,80){\vector(1,1){35}} 
\put(155,80){\vector(-1,1){35}} 
\put(40,30){\makebox(20,20)[]{1}} 
\put(120,30){\makebox(20,20)[]{2}} 
\put(135,70){\makebox(20,20)[]{3}} 
\put(80,70){\makebox(20,20)[]{4}} 
\put(95,70){\makebox(20,20)[]{5}} 
\put(35,115){\makebox(20,20)[]{7}} 
\put(75,115){\makebox(20,20)[]{6}} 
\put(120,110){\makebox(20,20)[]{8}} 
\put(230.25,220.25){\circle*{10}} 
\put(310.25,220.25){\circle*{10}} 
\put(270.25,180.25){\circle*{10}} 
\put(190.25,180.25){\circle*{10}} 
\put(190,180){\vector(1,1){35}} 
\put(270,180){\vector(-1,1){35}} 
\put(270,180){\vector(1,1){35}} 
\put(190.25,220.25){\circle*{10}} 
\put(270,180){\vector(-2,1){70}} 
\put(190,180){\line(1,2){20}} 
\put(190,180){\line(2,1){80}} 
\put(270,180){\vector(1,2){35}} 
\put(310.25,260.25){\circle*{10}} 
\put(230,220){\vector(2,1){70}} 
\put(230.25,260.25){\circle*{10}} 
\put(270,220){\vector(-1,1){35}} 
\put(210,220){\vector(-1,2){15}} 
\put(190.25,260.25){\circle*{10}} 
\put(230,220){\vector(-1,1){35}} 
\put(195,165){\makebox(20,20)[]{1}} 
\put(275,165){\makebox(20,20)[]{2}} 
\put(170,215){\makebox(20,20)[]{3}} 
\put(235,210){\makebox(20,20)[]{4}} 
\put(315,210){\makebox(20,20)[]{5}} 
\put(170,250){\makebox(20,20)[]{6}} 
\put(235,250){\makebox(20,20)[]{7}} 
\put(315,250){\makebox(20,20)[]{8}} 
\put(85.25,285.25){\circle*{10}} 
\put(25.25,225.25){\circle*{10}} 
\put(70.25,160.25){\circle*{10}} 
\put(145.25,230.25){\circle*{10}} 
\put(40.25,265.25){\circle*{10}} 
\put(125.25,265.25){\circle*{10}} 
\put(45.25,175.25){\circle*{10}} 
\put(125.25,175.25){\circle*{10}} 
\put(85,285){\vector(-1,-1){55}} 
\put(125,265){\vector(-1,0){80}} 
\put(125,265){\vector(1,-2){15}} 
\put(125,265){\vector(0,-1){80}} 
\put(85,285){\vector(-1,-3){35}} 
\put(125,175){\vector(-1,0){75}} 
\put(85,285){\vector(1,-3){35}} 
\put(125,265){\vector(-1,-2){50}} 
\put(125,175){\vector(-1,1){85}} 
\put(90,275){\makebox(20,20)[]{1}} 
\put(130,255){\makebox(20,20)[]{2}} 
\put(135,205){\makebox(20,20)[]{3}} 
\put(130,165){\makebox(20,20)[]{4}} 
\put(80,150){\makebox(20,20)[]{5}} 
\put(20,165){\makebox(20,20)[]{6}} 
\put(30,210){\makebox(20,20)[]{7}} 
\put(15,255){\makebox(20,20)[]{8}} 
\put(5,145){\makebox(30,20)[]{(a)}} 
\put(305,150){\makebox(30,20)[]{(b)}} 
\put(5,5){\makebox(30,20)[]{(c)}} 
\put(305,10){\makebox(30,20)[]{(d)}} 
\end{picture}
}

\newcommand{\ostrategy}
{
\begin{picture}(341,266) 
\put(50.25,245.25){\circle*{10}} 
\put(110.25,245.25){\circle*{10}} 
\put(50.25,215.25){\circle*{10}} 
\put(50.25,185.25){\circle*{10}} 
\put(110.25,215.25){\circle*{10}} 
\put(110.25,185.25){\circle*{10}} 
\put(50,245){\line(1,-1){60}} 
\put(50,245){\line(2,-1){60}} 
\put(50,215){\line(2,1){60}} 
\put(50,185){\line(1,1){60}} 
\put(50,215){\line(1,0){60}} 
\put(50,245){\line(1,0){60}} 
\put(50,215){\line(2,-1){60}} 
\put(50,185){\line(1,0){60}} 
\put(110,215){\line(-2,-1){60}} 
\put(185.25,255.25){\circle*{10}} 
\put(285.25,255.25){\circle*{10}} 
\put(215.25,215.25){\circle*{10}} 
\put(255.25,215.25){\circle*{10}} 
\put(285.25,175.25){\circle*{10}} 
\put(215,215){\line(1,0){40}} 
\put(215,215){\line(1,1){15}} 
\put(235.25,235.25){\circle{10}} 
\put(255,215){\line(-1,1){15}} 
\put(240,240){\line(3,1){45}} 
\put(255,215){\line(3,-4){30}} 
\put(185,255){\line(3,-1){45}} 
\put(185.25,175.25){\circle*{10}} 
\put(215,215){\line(-3,-4){30}} 
\put(235.25,175.25){\oval(100,20)[b]} 
\put(285.25,215.25){\oval(10,80)[r]} 
\put(185.25,215.25){\oval(10,80)[l]} 
\put(235.25,255.25){\oval(100,10)[t]} 
\put(40,40){\framebox(90,90){}} 
\put(40.25,130.25){\circle*{10}} 
\put(60,60){\line(1,0){55}} 
\put(40.25,100.25){\circle*{10}} 
\put(40,100){\line(1,0){15}} 
\put(60.25,100.25){\circle{10}} 
\put(60,95){\line(0,-1){55}} 
\put(115,40){\line(0,1){60}} 
\put(115,100){\line(-1,0){50}} 
\put(60.25,60.25){\circle*{10}} 
\put(60.25,40.25){\circle*{10}} 
\put(115.25,60.25){\circle*{10}} 
\put(115.25,40.25){\circle*{10}} 
\put(195,35){\framebox(90,90){}} 
\put(195,35){\framebox(60,60){}} 
\put(225,125){\line(0,-1){90}} 
\put(225.25,125.25){\circle*{10}} 
\put(195.25,95.25){\circle*{10}} 
\put(225.25,35.25){\circle*{10}} 
\put(255.25,65.25){\circle*{10}} 
\put(255.25,35.25){\circle*{10}} 
\put(225.25,65.25){\circle*{10}} 
\put(225,65){\line(1,0){30}} 
\put(70,155){\makebox(30,15)[t]{(a)}} 
\put(220,140){\makebox(30,15)[t]{(b)}} 
\put(70,15){\makebox(30,15)[t]{(c)}} 
\put(225,5){\makebox(30,15)[t]{(d)}} 
\put(285,125){\line(1,0){5}} 
\put(295,125){\line(1,0){5}} 
\put(285,35){\line(1,0){5}} 
\put(295,35){\line(1,0){5}} 
\put(190,35){\line(1,0){5}} 
\put(180,35){\line(1,0){5}} 
\put(180,65){\line(1,0){5}} 
\put(190,65){\line(1,0){5}} 
\put(210,65){\line(1,0){5}} 
\put(200,65){\line(1,0){5}} 
\put(180,125){\line(1,0){5}} 
\put(190,125){\line(1,0){5}} 
\put(295,95){\line(1,0){5}} 
\put(180,95){\line(1,0){5}} 
\put(255,95){\line(1,0){5}} 
\put(265,95){\line(1,0){5}} 
\put(285,95){\line(1,0){5}} 
\put(275,95){\line(1,0){5}} 
\put(265,65){\line(1,0){5}} 
\put(275,65){\line(1,0){5}} 
\put(295,65){\line(1,0){5}} 
\put(285,65){\line(1,0){5}} 
\put(255,135){\line(0,-1){5}} 
\put(255,125){\line(0,-1){5}} 
\put(255,115){\line(0,-1){5}} 
\put(255,105){\line(0,-1){5}} 
\put(225,135){\line(0,-1){5}} 
\put(195,135){\line(0,-1){5}} 
\put(285,135){\line(0,-1){5}} 
\put(225,30){\line(0,-1){5}} 
\put(285,30){\line(0,-1){5}} 
\put(255,30){\line(0,-1){5}} 
\put(195,30){\line(0,-1){5}} 
\end{picture} 
}

\newcommand{\incltip}
{
\begin{picture}(341,236) 
\put(35,135){\framebox(100,75){}} 
\put(20,45){\framebox(130,180){}} 
\put(50,155){\framebox(30,35){}} 
\put(95,155){\framebox(30,35){}} 
\put(20,210){\makebox(20,15)[t]{a}} 
\put(35,195){\makebox(20,15)[t]{b}} 
\put(50,175){\makebox(20,15)[t]{d}} 
\put(95,175){\makebox(20,15)[t]{e}} 
\put(35,60){\framebox(100,60){}} 
\put(80,70){\framebox(30,35){}} 
\put(35,105){\makebox(20,15)[t]{c}} 
\put(80,90){\makebox(20,15)[t]{f}} 
\put(225,195){\framebox(30,35){}} 
\put(190,140){\framebox(30,35){}} 
\put(260,140){\framebox(30,35){}} 
\put(215,40){\framebox(30,35){}} 
\put(260,85){\framebox(30,35){}} 
\put(240,195){\line(0,-1){10}} 
\put(205,185){\line(0,-1){10}} 
\put(275,185){\line(0,-1){10}} 
\put(275,140){\line(0,-1){20}} 
\put(215,85){\framebox(30,35){}} 
\put(205,185){\line(1,0){70}} 
\put(205,60){\line(1,0){10}} 
\put(205,105){\line(1,0){10}} 
\put(205,140){\line(0,-1){80}} 
\put(225,215){\makebox(20,15)[t]{a}} 
\put(190,160){\makebox(20,15)[t]{b}} 
\put(215,105){\makebox(20,15)[t]{d}} 
\put(215,60){\makebox(20,15)[t]{e}} 
\put(260,160){\makebox(20,15)[t]{c}} 
\put(260,105){\makebox(20,15)[t]{f}} 
\put(70,5){\makebox(30,15)[t]{(a)}} 
\put(235,5){\makebox(30,15)[t]{(b)}} 
\end{picture} 
}


\newcommand{\nonupward}
{
\begin{picture}(341,141) 
\put(120.25,40.25){\circle*{10}} 
\put(180.25,100.25){\circle*{10}} 
\put(120,40){\vector(1,1){55}} 
\put(180.25,40.25){\circle*{10}} 
\put(120.25,100.25){\circle*{10}} 
\put(150.25,130.25){\circle*{10}} 
\put(150.25,10.25){\circle*{10}} 
\put(150,10){\vector(-1,1){25}} 
\put(150,10){\vector(1,1){25}} 
\put(180,40){\vector(-1,1){55}} 
\put(120,40){\vector(0,1){55}} 
\put(180,40){\vector(0,1){55}} 
\put(120,100){\vector(1,1){25}} 
\put(180,100){\vector(-1,1){25}} 
\end{picture} 
}

\fi

\ifesp \else

\setlength{\topmargin}{-0.5in}
% \setlength{\parskip}{10pt}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
% \setlength{\parindent}{0mm}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{\oddsidemargin}

\fi

\newcounter{paperno} \setcounter{paperno}{0}
\newcounter{current} \setcounter{current}{0}
\newenvironment{paper}{\begin{enumerate}
\setcounter{current}{\value{paperno}}\stepcounter{current}
\item[\thecurrent.]\refstepcounter{paperno}\small}{\end{enumerate}}

% -----------------------------------------------------------------------

 
\begin{document}
 
% -------------------------------------------------------------------
 
\ifesp

\begin{frontmatter}

\title{Algorithms for Drawing Graphs: \\ an Annotated Bibliography}
%
\author{Giuseppe Di Battista}
%
\address{Dipartimento di Informatica e Sistemistica, 
Universit\`a di Roma ``La Sapienza,'' 
Via Salaria 113,  Roma, 
00198 Italy, 
{\tt dibattista@iasi.rm.cnr.it}}
%
\author{Peter Eades}
%
\address{Department of Computer Science, 
University of Newcastle, 
University Drive, Callaghan, 
NSW 2308, Australia, 
{\tt eades@cs.newcastle.edu.au}}
%
\author{Roberto Tamassia}
%
\address{Department of Computer Science, 
Brown University, 
Providence, RI 02912--1910, 
USA, 
{\tt rt@cs.brown.edu}}
%
\author{Ioannis G. Tollis}
%
\address{Department of Computer Science, 
The University of Texas at Dallas, 
Richardson, Texas 75083--0688, 
USA, 
{\tt tollis@utdallas.edu}}
%
\else

\begin{titlepage}
 
\maketitle

\fi
%
\begin{abstract}
Several data presentation problems involve drawing graphs so that they
are easy to read and understand. Examples include circuit schematics
and software engineering diagrams. In this paper we present a
bibliographic survey on algorithms whose goal is to produce
aesthetically pleasing drawings of graphs. Research on this topic is
spread over the broad spectrum of Computer Science. This bibliography
constitutes an attempt to encompass both theoretical and application
oriented papers from disparate areas.
\end{abstract}
%
\ifesp
%
\end{frontmatter}
%
\else
 
\thispagestyle{empty}
 
\end{titlepage}

\tableofcontents

\sloppy

\clearpage
\fi


% -------------------------------------------------------------------

\section{Introduction}
 
A number of data presentation problems involve the drawing of a graph
on a two-dimensional surface.  Examples include circuit schematics,
algorithm animation, and software engineering. In this paper we present
a bibliographic survey on algorithms whose goal is to produce clear and
readable drawings of graphs.
 
Various {\em graphic standards} have been proposed for the
representation of graphs in the plane. Usually, the vertices are
represented by symbols such as circles or boxes, and each edge $(u,v)$
is represented by a simple open curve between the symbols associated
with the vertices $u$ and $v$.
 
A drawing such that each edge is represented by a polygonal chain is a
{\em polyline} drawing (see Fig.~\ref{fi-z}). There are two common
special cases of this standard. A {\em straight-line} drawing maps each
edge into a straight-line segment (see Fig.~\ref{fi-s}). This standard
is commonly adopted in graph theory texts. An {\em orthogonal} drawing
maps each edge into a chain of horizontal and vertical segments (see
Fig.~\ref{fi-b}). Entity Relationship diagrams in data base design are
usually drawn according to this standard.  Note that polyline drawings
can be modified to give drawings with nicely curved edges.  A drawing
is {\em planar} if no two edges intersect. A polyline drawing is a {\em
grid} drawing if the vertices and the bends of the edges have integer
coordinates.
 
\iffig \begin{figure}[hb] %  z 2.4in
\centering\poly
\caption{ Polyline drawing.}
\label{fi-z}
\end{figure} \fi
 
\iffig \begin{figure}[hb] %  s 2.3in
\centering\straight
\caption{Straight-line drawing.}
\label{fi-s}
\end{figure} \fi
 
A {\em graph drawing algorithm} reads as input a combinatorial
description of a graph $G$, and produces as output a drawing of $G$
according to a given graphic standard.  The drawing is described in
terms of graphics primitives such as {\sc draw\_line} and {\sc
fill\_circle}, which can be interpreted on a physical graphics device.
 
Within a graphic standard, a graph has infinitely many different
drawings. However, in almost all data presentation applications, the
usefulness of a drawing of a graph depends on its readability, that is,
the capability of conveying the meaning of the diagram quickly and
clearly. Readability issues are expressed by means of {\em aesthetics},
which can be formulated as optimization goals for the drawing
algorithms. In general, the aesthetics depend on the graphic standard
adopted and the particular class of graphs of interest. A fundamental
and classical aesthetic is the minimization of crossings between
edges.  In polyline drawings it is desirable to avoid bends in edges.
In grid drawings, the area of the smallest rectangle covering the
drawing should be minimal. In all graphic standards, the display of
symmetries is desirable. It should be noted that aesthetics are
subjective and may need to be tailored to suit personal preferences,
traditions and culture.  For example, although the cube graph is
planar, it is traditionally drawn with crossing edges, as shown in
Fig.~\ref{fi-q}.
 
\iffig \begin{figure}[hb] %  b 2.75in
\centering\ortho
\caption{Orthogonal drawing.}
\label{fi-b}
\end{figure} \fi
 
\iffig \begin{figure}[hb] %  q 2.5in
\centering\cube
\caption{Two drawings of the cube graph.}
\label{fi-q}
\end{figure} \fi
 
Research on graph drawing algorithms is spread over the broad spectrum
of Computer Science, from VLSI to data base design. This bibliography
constitutes a first attempt to encompass both theoretical and
application oriented papers from disparate areas. However, we do not
consider layout algorithms (such as some VLSI layout techniques) that
have no impact on the problem of producing aesthetically pleasing
drawings. As indicated in the title, this bibliography concentrates on
{\em algorithms} for drawing graphs. It is written from a Computer
Science viewpoint, and does not deal with other aspects of the problem
of drawing graphs. Namely, we do not attempt to cover the large
literature on the mathematical theory of embeddings of graphs, work on
circuit and facilities layout, or psychological and philosophical
issues of aesthetically pleasing drawings.  We have omitted many papers
which describe graphic user interfaces and visualization systems;
although these often use graph drawings, few currently have automatic
layout facilities.  However, introductory textbooks on graphs and
algorithms, and a few significant papers from related areas have been
included for the reader's convenience.
 
In Section~\ref{se-prel} we mention background reference material for
graph drawing problems. Sections~\ref{se-trees}, \ref{se-ugraphs},
\ref{se-planar}, and~\ref{se-digraphs} consider in turn algorithms for
drawing trees, general graphs, planar graphs and directed graphs.
Literature on systems which use graph layout algorithms is outlined in
Section~\ref{se-systems}.  Papers on topics that do not fit the above
classification are mentioned in Section~\ref{se-other}.  A list of
significant open problems is given in Section~\ref{se-open}.  The talks
given at {\em Graph Drawing '93} are listed in Appendix~\ref{app-gd}.
Appendix~\ref{app-gdd} contains the call for papers of {\em Graph
Drawing '94}.  An index of authors is provided in
Appendix~\ref{app-index}.

Throughout the paper $n$ and $m$ denote the number of vertices and
edges of the graph currently being considered.
 
% -------------------------------------------------------------------
 
\section{Background} \label{se-prel}
 
For elementary graph theory, the following textbooks may be
consulted
 
\begin{paper}
J.A.\ Bondy and U.S.R.\ Murty, Graph Theory with Applications,
North Holland, Amsterdam, 1976.
\label{pa-RA} \end{paper}
 
\begin{paper}
F.\ Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
\label{pa-RB} \end{paper}
 
Fundamentals of data structures and algorithms are described in
 
\begin{paper}
E.\ Horowitz and S.\ Sahni, Fundamentals of Data Structures,
Computer Science Press, 1983.
 
\label{pa-SA} \end{paper}
 
\begin{paper}
T.H.\ Cormen, C.E.\ Leiserson, and R.L.\ Rivest,
Introduction to Algorithms, The MIT Press, 1990.
\label{pa-PDE0} \end{paper}
 
\begin{paper}
E.M.\ Reingold, J.\ Nievergelt, and N.\ Deo, Combinatorial
Algorithms: Theory and Practice, Prentice Hall, 1977. 
\label{pa-SB} \end{paper}

Algorithms for graph problems and applications are described in

\begin{paper}
S.\ Even, Graph Algorithms, Computer Science Press, Potomac, MD,
1979.
\label{pa-RC} \end{paper}

\begin{paper}
A.\ Gibbons, Algorithmic Graph Theory, Cambridge University Press,
Cambridge, Great Britain, 1985.
\label{pa-Gib85} \end{paper}

\begin{paper}
J.A.\ McHugh, Algorithmic Graph Theory, Prentice Hall,
Englewood Cliffs, NJ, 1990.
\label{pa-Mc90} \end{paper}
 
\begin{paper}
R.E.\ Tarjan, ``Data Structures and Network Algorithms,'' CBMS-NSF
Regional Conference Series in Applied Mathematics, vol.\ 44,
Society for Industrial Applied Mathematics, 1983.
\label{pa-ZX} \end{paper}

Algorithms for planar graphs are presented in:
 
\begin{paper}
T.\ Nishizeki and N.\ Chiba, Planar Graphs: Theory and Algorithms,
Annals of Discrete Mathematics 32, North-Holland, 1988.
\label{pa-ZY} \end{paper}
 
Concepts and applications of NP-completeness and complexity theory
are described in
 
\begin{paper}
M.R.\ Garey and D.S.\ Johnson, Computers and Intractability: A
Guide to the Theory of NP-Completeness, Freeman, 1979.
 
\label{pa-SC} \end{paper}
Basic concepts of computer graphics and computational geometry are
given in
 
\begin{paper}
J.D.\ Foley, A.\ van Dam, S.K.\ Feiner, and J.F.\ Hughes, ``Computer
Graphics: Principles and Practice,'' Addison-Wesley, 1990.
\label{pa-SD} \end{paper}
 
\begin{paper}
F.P.\ Preparata and M.I.\ Shamos, Computational Geometry,
Springer-Verlag, New York, 1985.
\label{pa-SE} \end{paper}
 
Two previous versions of this bibliography have appeared as:

\begin{paper}
P. \  Eades and R. \  Tamassia, ``Algorithms for Drawing Graphs: An
Annotated Bibliography,'' Technical Report 82, Department of Computer
Science, University of Queensland 1987.
\label{pa-PDE1} \end{paper}
 
\begin{paper}
P. \  Eades and R. \  Tamassia, ``Algorithms for Drawing Graphs: An
Annotated Bibliography,'' Technical Report CS-09-89, Department of
Computer Science, Brown University 1989.
\label{pa-PDE2} \end{paper}


Many abstracts of recent papers on graph drawing appear in

\begin{paper}
G.\ Di Battista, H.\ de Fraysseix, P.\ Eades, P.\ Rosenstiehl, and
R.\ Tamassia (Editors), {\em Graph Drawing'93}, Proc.\ ALCOM
International Workshop on Graph Drawing and Topological Graph
Algorithms, S\`evres, Parc of Saint Cloud, Paris, September 25--29,
1993.  Available by anonymous ftp from {\tt wilma.cs.brown.edu}, {\tt
/pub/papers/compgeo/gd93.tex.Z}, {\tt
/pub/papers/compgeo/gd93.ps.Z}.
\label{pa-GD93} \end{paper}

The talks presented at Graph Drawing'93 are listed in
Appendix~\ref{app-gd}.

 
% -------------------------------------------------------------------
 
\section{Trees} \label{se-trees}

\subsection{Rooted Trees}

Rooted trees are often used to represent hierarchies such as family
trees, organization charts, and search trees. Planar straight-line
drawings and orthogonal polyline drawings are commonly used to
represent rooted trees (see Fig.~\ref{fi-e}).  The following additional
aesthetics are often adopted.

\begin{itemize}

\item Vertices are placed along horizontal lines according to their
level (graph-theoretic distance from the root).

\item There is a minimum separation distance between two consecutive
vertices on the same level.

\item The width of the drawing is as small as possible.

\end{itemize}

Further, for ordered binary trees such as search trees,
we require:

\begin{itemize}

\item The left and right children of each vertex $v$ are placed to the
left and right of $v$, respectively.

\end{itemize}

\iffig \begin{figure}[hbt] %  e 2.4in
\centering\tree
\caption{Drawings of a rooted tree
in straight line and polyline orthogonal standards.}
\label{fi-e}
\end{figure} \fi

The following papers contain heuristics for drawing rooted trees that
address the above aesthetics. Additional aesthetics, such as centering
each parent upon its children, and generating congruent drawings for
isomorphic subtrees, are also investigated.

\begin{paper}
R.E.\ Sweet, ``Empirical Estimates of Program Entropy,'' Technical
Report STAN-CS-78-698, Stanford Univ., Stanford, CA, 1978.
\label{pa-XA} \end{paper}
 
\begin{paper}
C.\ Wetherell and A.\ Shannon, ``Tidy Drawing of Trees,'' IEEE Trans.
on Software Engineering, vol.\ SE-5, no.\ 5, pp.\ 514-520,
1979.
\label{pa-XB} \end{paper}
 
\begin{paper}
J.\ Vaucher, ``Pretty Printing of Trees,'' Software Practice and
Experience, vol.\ 10, no.\ 7, pp.\ 553-561, 1980.
\label{pa-XC} \end{paper}

\begin{paper}
E.\ Reingold and J.\ Tilford, ``Tidier Drawing of Trees,'' IEEE
Trans.\ on Software Engineering, vol.\ SE-7, no.\ 2, pp.\ 223-
228, 1981.
\label{pa-XD} \end{paper}

\begin{paper}
J.S.\ Tilford, ``Tree Drawing Algorithms,'' Technical Report
UIUCDCS-R-81-1055, Dept.\ of Computer Science, Univ.\ of
Illinois at Urbana-Champaign, 1981.
\label{pa-XE} \end{paper}

\begin{paper}
J.Q. Walker II, ``A Node-positioning Algorithm for General Trees,''
Software Practice and Experience, vol.\ 20, no.\ 7, pp.\ 685-705,
1990.
\label{pa-W90} \end{paper}

Implementation details of a variation of the algorithm by Reingold and
Tilford [\ref{pa-XD}] are discussed by Brueggemann-Klein and Wood;
the paper presents a set of {\em TeX} macros to implement
the algorithm.
 
\begin{paper}
A. Brueggemann-Klein and D. Wood, Drawings Trees Nicely with \TeX,
Electronic Publishing, Origination, Dissemination, and Design, vol. 2,
pp. 101-115 (1989).
\label{pa-WL} \end{paper}

The extension of these algorithms to rooted trees with arbitrary vertex
degree is straightforward.  The algorithms give aesthetically
acceptable drawings. However, Supowit and Reingold show that they can
produce drawings much wider than necessary.
 
\begin{paper}
K.J.\ Supowit and E.M.\ Reingold, ``The Complexity of Drawing Trees
Nicely,'' Acta Informatica, vol.\ 18, pp.\ 377-392, 1983.
\label{pa-XF} \end{paper}

This paper addresses the problem of constructing a minimum width
drawing of a binary tree such that parents are centered upon their
children and isomorphic subtrees are congruent. This problem is
NP-complete if a grid drawing is required, but otherwise polynomially
solvable by linear programming techniques.
 
The area requirement of straight-line and polyline grid drawings of
binary and rooted trees is investigated in:
 
\begin{paper}
P.\ Crescenzi, G.\ Di Battista, and A.\ Piperno ``A Note on Optimal
Area Algorithms for Upward Drawings of Binary Trees,''
Computational Geometry: Theory and Applications, vol.\ 2,
pp.\ 187-200, 1992.
\label{pa-P2} \end{paper}

\begin{paper}
A.\ Garg, M.T.\ Goodrich and R.\ Tamassia, ``Area-Efficient Upward Tree
Drawings,'' Proc.\ ACM Symp.\ on Computational Geometry, pp.\ 359-368,
1993.
\label{pa-GGT93} \end{paper}
 
Three drawing conventions that are appealing for their practical
applicability are investigated in:
 
\begin{paper}
P.\ Eades, T.\ Lin, and X.\ Lin, ``Two Tree Drawing Conventions,''
International Journal of Computational Geometry and Applications,
vol. 3, no. 2, pp 133 - 153, 1993.
\label{pa-P1} \end{paper}

\begin{paper}
P.\ Eades, T.\ Lin, and X.\ Lin, ``Minimum Size h-v Drawings,''
Advanced Visual Interfaces (Proc.\ AVI 92), World Scientific
Series in Computer Science Volume 36, 386-394.
\label{pa-PDE3} \end{paper}
 
In the {\em inclusion} convention nodes are represented by boxes and
parent-child relationships are represented by inclusion of one box in
another.  The {\em tip-over} convention is similar to the classical
one, however, children of some nodes may be arranged vertically rather
than horizontally.  An {h-v drawing} is similar to a tip-over drawing.
Examples of inclusion and tip-over drawings are in Fig.~\ref{fi-PDE4}.
 
\iffig \begin{figure}[htb] %  b 2.75in
\centering\incltip
\caption{Inclusion and tip-over conventions.}
\label{fi-PDE4}
\end{figure} \fi

% -------------------------------------------------------------------
 
\subsection{Free Trees}
 
``Free'' trees do not represent hierarchies and have no specific root.
The above algorithms for rooted trees can be modified to produce
acceptable {\em radial} drawings of free trees by arranging the
vertices of each level on a concentric circle about the graphtheoretic
center of the tree.  Folklore on radial and other simple drawings of
free trees is summarized in
 
\begin{paper}
P.D.\ Eades, ``Drawing Free Trees,'' Bulletin of the Institute for
Combinatorics and its Applications, vol. 5, 1992, 10-36.
\label{pa-PDE5} \end{paper}
 
Strategies for constructing radial drawings are described in
 
\begin{paper}
M.A.\ Bernard, ``On the Automated Drawing of Graphs,'' Prc.\ 3rd
Caribbean Conf.\ on Combinatorics and Computing, pp.\ 43-55,
1981.
\label{pa-QX} \end{paper}
 
\begin{paper}
T.\ Kamada, Visualizing Abstract Objects and Relations, World
Scientific, 1989.
\label{pa-P47} \end{paper}
 
The following paper shows how to display symmetries in radial drawings.
 
\begin{paper}
J.\ Manning and M.J.\ Atallah, ``Fast Detection and Display of
Symmetry in Trees,'' Congressus Numerantium, vol.\ 64, pp.
159-169, 1988.
\label{pa-XG} \end{paper}
 
Bhatt and Cosmadakis show that it is NP-complete to construct an
orthogonal grid drawing of a tree such that the maximum edge length is
minimized:
 
\begin{paper}
S.\ Bhatt and S.\ Cosmadakis, ``The Complexity of Minimizing Wire
Lengths in VLSI Layouts,'' Information Processing Letters,
vol.\ 25, pp.\ 263-267, 1987.
\label{pa-WC} \end{paper}
 
The techniques of Bhatt and Cosmodakis are refined and extended
in the following:
 
\begin{paper}
F.J.\ Brandenburg, ``Nice Drawings of Graphs and Trees are
Computationally Hard,'' Technical Report MIP-8820, Fakult\"at f\"ur
Mathematik und Informatik, Univ.\ Passau, 1988.
\label{pa-RM} \end{paper}
 
\begin{paper}
A.\ Gregori, ``Unit Length Embedding of Binary Trees on a Square
Grid,'' Information Processing Letters, vol.\ 31, pp.\ 167-172, 1989.
\label{pa-PDE6} \end{paper}

\begin{paper}
P. J. \ Idicula, ``Drawing Trees in Grids,'' Masters Thesis, Department
of Computer Science, University of Auckland 1990.
\label{pa-PDE7} \end{paper}
 

% -------------------------------------------------------------------

\section{General Graphs} \label{se-ugraphs}
 
There are several aesthetics for obtaining attractive drawings of
general undirected graphs.  The main such aesthetics are:

\begin{itemize}
 
\item display symmetry;
 
\item avoid edge crossings;
 
\item avoid bends in edges;
 
\item keep edge lengths uniform;
 
\item distribute vertices uniformly.
 
\end{itemize}
 
In general, the optimization problems associated with these aesthetics
are NP-hard. Several complexity results are reported in:
 
\begin{paper}
D.S.\ Johnson, ``The NP-Completeness Column: an Ongoing Guide,'' J.
of Algorithms, vol.\ 3, no.\ 1, pp.\ 89-99, 1982.
\label{pa-ZJ} \end{paper}
 
\begin{paper}
D.S.\ Johnson, ``The NP-Completeness Column: an Ongoing Guide,'' J.
of Algorithms, vol.\ 5, no.\ 2, pp.\ 147-160, 1984.
\label{pa-ZK} \end{paper}
 
Many problems are NP-hard even for restricted classes of graphs,
such as trees and planar graphs. Specific results are presented in
[\ref{pa-XF}, \ref{pa-P1}, \ref{pa-WC}, \ref{pa-RM}, \ref{pa-PDE6},
\ref{pa-PDE7}, \ref{pa-YB}] and:
 
\begin{paper}
M.R.\ Garey and D.S.\ Johnson, ``Crossing Number is NP-Complete,''
SIAM J.\ Algebraic and Discrete Methods, vol.\ 4, no.\ 3, pp.
312-316, 1983.
\label{pa-ZL} \end{paper}
 
\begin{paper}
M.R.\ Kramer and J.\ van Leeuwen, ``The Complexity of Wire-Routing
and Finding Minimum Area Layouts for Arbitrary VLSI
Circuits,'' in Advances in Computing Research, vol.\ 2, ed.
F.P.\ Preparata, pp.\ 129-146, JAI Press, Greenwich, CT, 1984.
\label{pa-ZM} \end{paper}
 
\begin{paper}
Z.\ Miller and J.B.\ Orlin, ``NP-Completeness for Minimizing Maximum
Edge Length in Grid Embeddings,'' J.\ Algorithms, vol.\ 6, pp.
10-16, 1985.
\label{pa-SM} \end{paper}
 
Besides time complexity limitations, the above aesthetics are also
``competitive'' in that the optimality of one often prevents the
optimality of others. Because of such difficulties, general
approaches to graph drawing are usually heuristic.

% -------------------------------------------------------------------
 
\subsection{Straight-Line Drawings}
 
A model for measuring the symmetry of a straight-line drawing of a
graph is given in:
 
\begin{paper}
R.\ Lipton, S.\ North, and J.\ Sandberg, ``A Method for Drawing
Graphs,'' Proc.\ ACM Symp.\ on Computational Geometry, pp.
153-160, 1985.
\label{pa-ZN} \end{paper}
 
This paper also proposes an algorithm for constructing a straight-line
drawing of a graph with as much symmetry as possible; however the
algorithm requires the solution of the apparently intractable problem
of computing the automorphism group of a graph. A completely different
approach to symmetry display (which avoids computing automorphisms) is
described in:
 
\begin{paper}
P.\ Eades, ``A Heuristic for Graph Drawing,'' Congressus
Numerantium, vol.\ 42, pp.\ 149-160, 1984.
\label{pa-ZO} \end{paper}
This algorithm, called {\em spring embedder}, is a heuristic based on a
physical model. The straight-line standard is adopted. The drawing
process is to simulate a mechanical system, where vertices are replaced
by rings, and edges are replaced by springs. The springs attract the
rings if they are too far apart, and repel them if they are too close.
 
The algorithms of [\ref{pa-XO}, \ref{pa-XP}, \ref{pa-XT}, \ref{pa-XU}]
may be viewed as spring algorithms with the positions of some of the
vertices fixed; although originally designed for planar graphs, they
may be applied to nonplanar graphs with reasonable results.
 
Other algorithms of a similar ``force directed''
nature are described in [\ref{pa-P47}] and

\begin{paper}
J.E.\ Cuny, D.A.\ Bayley, J.W.\ Hagerman, and A.A.\ Hough, ``The
Simple Simon Programming Environment: A Status Report,''
Technical Report 87-22, Dept.\ of Computer and Information
Science, Univ.\ of Massachusetts, Amherst, MA, May 1987.
\label{pa-R7}
\end{paper}
 
\begin{paper}
T.\ Kamada and S.\ Kawai, ``Automatic Display of Network Structures
for Human Understanding,'' Technical Report 88-007, Dept.\ of
Information Science, Univ.\ of Tokyo, 1988.
\label{pa-WG}
\end{paper}
 
\begin{paper}
T.\ Kamada, ``On Visualization of Abstract Objects and Relations,''
Ph.D.\ dissertation, Dept.\ of Information Science, Univ.\ of
Tokyo, 1988.
\label{pa-UA}
\end{paper}
 
\begin{paper}
T.\ Kamada and S.\ Kawai, ``An Algorithm for Drawing General
Undirected Graphs,'' Information Processing Letters, vol.\ 31,
pp.\ 7-15, 1989.
\label{pa-WW}
\end{paper}
 
\begin{paper}
T.\ Kamada, ``Symmetric Graph Drawing by a Spring Algorithm and its
Applications to Radial Drawing,'' Manuscript, Dept.\ of
Information Science, Univ.\ of Tokyo, 1989.
\label{pa-QK}
\end{paper}
 
\begin{paper}
T.\ Fruchterman and E.\ Reingold, ``Graph Drawing by Force-Directed
Placement,'' Software-Practice and Experience, vol.\ 21, no.\ 11,
pp.\ 1129-1164, 1991.
\label{pa-P25} \end{paper}

A general model for spring algorithms is defined in [\ref{pa-PDEf}];
this thesis also attempts to explain mathematically the apparent
connection between spring algorithms and symmetrical drawings.

An extension of the spring approach is presented by Davidson and Harel.
An energy function is defined in terms of the desired aesthetics:
for instance, the number of edge crossings plus a measure of the closeness
of vertices. A layout of minimal energy (an thus maximal
beauty according to the energy function) is obtained
by simulated annealing.

\begin{paper}
R.\ Davidson and D.\ Harel, ``Drawing Graphs Nicely Using Simulated
Annealing,'' Technical Report CS 89--13, Department of Applied
Mathematics and Computer Science, The Weizmann Institute of Science,
Rehovot, 1989 (revised July 1993, to appear in Communications ACM).
\label{pa-PDEq}
\end{paper}

An algorithm based on multidimensional scaling (a standard statistical
method) that finds a placement of vertices with euclidean distances
that approximate the graph-theoretic distances is presented in

\begin{paper}
J.B.\ Kruskal and J.B.\ Seery, ``Designing Network Diagrams,''
Proc.\ First General Conference on Social Graphics, U.\ S.\ Department
of the Census, Washington, D.C., pp.\ 22-50, July 1980.
\label{pa-Kru}
\end{paper}

An algorithm that uses several heuristics to obtain ``near-optimal''
drawings is presented by Tunkelang.  The heuristics improve on existing
approaches by focusing on three aspects of the graph drawing problem:
computation of the aesthetic cost of a drawing, order of node
placement, and local optimization techniques.  The algorithm and
comparison with the techniques of [\ref{pa-P25}] and [\ref{pa-PDEq}]
are described in:

\begin{paper}
D.\ Tunkelang, ``An Aesthetic Layout Algorithm for Undirected Graphs,''
M.S. Thesis, Department of Electrical Engineering and Computer Science,
MIT, 1992.
\label{pa-Tun92}
\end{paper}

A simple heuristic for constructing straight-line drawings which adds
one vertex at a time is described in:
 
\begin{paper}
H.\ Watanabe, ``Heuristic Graph Displayer for G-BASE,'' Technical
Report no.\ 17, Ricoh Software Research Center, Tokyo, Japan,
1988.
 
\label{pa-QZ} \end{paper}
 
M\"akinen considers straight-line drawings with vertices placed along
the circumference of a circle. He shows that several related
optimization problems are NP-complete and gives a heuristic for
reducing the maximum edge length.
 
\begin{paper}
E.\ M\"akinen, ``On Circular Layouts,'' Int.\ Journal of Computer
Mathematics, vol.\ 24, pp.\ 29-37, 1988.
\label{pa-WJ} \end{paper}

% -------------------------------------------------------------------
 
\subsection{Planarization} \label{se-planarization}

As discussed above, most of the techniques for drawing general
undirected graphs are heuristics based on various types of simulation.
Given the wealth of techniques available for drawing planar graphs, a
sensible strategy for drawing a nonplanar graph is to first {\em
planarize} the graph, and then apply a planar graph drawing algorithm.
Significant examples of this strategy are presented
in~[\ref{pa-KA1},\ref{pa-R6}].  The term {\em planarization} is used
for several related problems.  In general, planarization seeks to
transform a nonplanar graph into a planar graph with a small number of
well defined operations.
 
The most common planarization operation is {\em edge deletion}:  one
must find a small number of edges whose deletion yields a planar
graph.  This is equivalent to finding a planar subgraph with a large
number of edges.  Finding a planar subgraph with a maximum number of
edges is NP-hard.  However, a maximal planar subgraph can be found
efficiently, as shown in~[\ref{pa-RS}] and:
 
\begin{paper}
J.\ Cai, X.\ Han, and R.E.\ Tarjan, ``An $O(m \log n)$-time Algorithm
for the Maximal Subgraph Problem,'' SIAM J.\ on Computing, to appear.
\label{pa-P43} \end{paper}

Heuristics for finding a maximum planar subgraph and algorithms for
finding a maximal planar subgraph are presented in:

\begin{paper}
M.\ Marek-Sadowska, ``Planarization Algorithms for Integrated
Circuits Engineering,'' Proc.\ IEEE Int.\ Symp.\ on Circuits and
Systems, pp.\ 919-923, 1978.
\label{pa-ZP} \end{paper}

\begin{paper}
N.\ Chiba, I.\ Nishioka, and I.\ Shirakawa, ``An Algorithm of Maximal
Planarization of Graphs,'' Proc.\ IEEE Int.\ Symp.\ on Circuits
and Systems, pp.\ 649-652, 1979.
\label{pa-ZQ} \end{paper}

\begin{paper}
E.\ Nardelli and M.\ Talamo, ``A Fast Algorithm for Planarization of
Sparse Diagrams,'' Technical Report R.105, IASI-CNR, Rome,
1984.
\label{pa-ZR} \end{paper}

\begin{paper}
T.\ Ozawa and H.\ Takahashi, ``A Graph-planarization Algorithm and
its Applications to Random Graphs,'' Graph Theory and
Algorithms, Lecture Notes in Computer Science, vol.\ 108, pp.
95-107, 1981.
\label{pa-ZS} \end{paper}

\begin{paper}
R.\ Jayakumar, K.\ Thulasiraman, and M.N.S.\ Swamy,
``On Maximal Planarization of Nonplanar Graphs,''
IEEE Trans.  Circuits and Systems, vol.\ CAS-33, no.\ 8, 843--854, 1986.
% ``An Optimal Algorithm for Maximal Planarization of Nonplanar Graphs,''
% Proc.\ 1986 IEEE Int.\ Symp.\ on Circuits and Systems, pp.
% 1237-1240, 1986.
\label{pa-ZT} \end{paper}

\begin{paper}
R.\ Jayakumar, K.\ Thulasiraman, and M.N.S Swamy, ``$O(n^2)$ Algorithms
for Graph Planarization,'' Technical Report CSD-88-01, Dept.
Computer Science, Concordia Univ., 1988.
\label{pa-RU} \end{paper}

\begin{paper}
G.\ Kant, ``An $O(n^2)$ Maximal Planarization Algorithm based on PQ-trees,''
Technical Report RUU-CS-92-03, Department of Computer Science, Utrecht
Univ., The Netherlands, 1992.
\label{pa-P13} \end{paper}

\begin{paper}
L.R.\ Foulds, P.B.\ Gibbons, and J.W.\ Giffin, ``Graph Theoretic
Heuristics for the Facilities Layout Problem: An Experimental
Comparison,'' Operations Research, 1985.
\label{pa-ZU} \end{paper}

\begin{paper}
P.\ Eades, L.\ Foulds, and J.\ Giffin, ``An Efficient Heuristic for
Identifying a Maximal Weight Planar Subgraph,'' Combinatorial
Mathematics IX, Lecture Notes in Mathematics, vol.\ 952, pp.
239-251, 1982.
\label{pa-ZV} \end{paper}

\begin{paper}
O.\ Goldschmidt and A.\ Takvorian, ``An Efficient Graph Planarization
Two-Phase Heuristic,'' Technical Report ORP91-01, Dept.\ of Mechanical
Engineering, Univ.\ Texas at Austin, 1991.
\label{pa-Takvorian} \end{paper}

\begin{paper}
M.\ J\"unger and P.\ Mutzel, ``Solving the Maximum Weight Planar
Subgraph Problem,'' Proc.\ 3rd Integer Programming and Combinatorial
Optimization Conf., pp. 479-492, 1993.
\label{pa-Mutzel} \end{paper}
 
Another planarization technique is to find a drawing with the minimum
number of crossings.  Again, this problem is NP-hard [\ref{pa-ZL}].
Heuristics for crossing minimization are given in:
 
\begin{paper}
D.\ Ferrari and L.\ Mezzalira, ``On Drawing a Graph with the Minimum
Number of Crossings,'' Technical Report n.\ 69-11, Istituto di
Elettrotecnica ed Elettronica, Politecnico di Milano, 1969.
\label{pa-ZZ} \end{paper}
  
A new technique for planarization is ``splitting''.  The {\em
splitting} operation is to make two copies of a vertex and share the
neighbors between the two copies.  This technique is used in manual
layout to simplify complex graphs.  A {\em minimum splitting sequence}
is a minimum length sequence of splittings which makes the graph
planar. Heuristics for finding a minimum splitting sequence are
discussed in
 
\begin{paper}
C.X.\ Mendon\c{c}a, ``Heuristics for Planarization by Vertex
Splitting,'' manuscript, University of Newcastle 1992.
\label{pa-PDEr} \end{paper}
 
The topological equivalence among nonplanar drawings of a graph is
studied in:
 
\begin{paper}
R.B.\ Eggleton, ``Rectilinear Drawings of Graphs,'' Utilitas
Mathematica, vol.\ 29, pp.\ 146-172, 1986.
 
\label{pa-QA} \end{paper}
 
There is an extensive mathematical literature on crossing numbers of
graphs, see the following papers for references:
 
\begin{paper}
H.\ Harborth and I.\ Mengersen, ``Edges Without Crossings in
Drawings of Complete Graphs,'' J.\ Combinatorial Theory (B),
vol.\ 17, no.\ 3, pp.\ 229-311, 1974.
\label{pa-RN} \end{paper}
 
\begin{paper}
R.K.\ Guy, ``Crossing Numbers of Graphs,'' Graph Theory and
Applications, Lecture Notes in Mathematics, vol.\ 303, pp.
111-124, 1972. 
\label{pa-RZ} \end{paper}
 
% -------------------------------------------------------------------
 
\subsection{Polyline Drawings} \label{se-polyline}
 
A comprehensive approach to the construction of orthogonal grid
drawings, based on a number of graph algorithms, is presented in:
 
\begin{paper}
C.\ Batini, E.\ Nardelli, M.\ Talamo, and R.\ Tamassia, ``A
Graphtheoretic Approach to Aesthetic Layout of Information
Systems Diagrams,'' Proc.\ 10th Int.\ Workshop on
Graphtheoretic Concepts in Computer Science (Berlin, June
1984), pp.\ 9-18, Trauner Verlag, 1984.
\label{pa-QB} \end{paper}
 
\begin{paper}
R.\ Tamassia, G.\ Di Battista, and C.\ Batini, ``Automatic Graph
Drawing and Readability of Diagrams,'' IEEE Transactions on
Systems, Man and Cybernetics, vol.\ SMC-18, no.\ 1, pp.\ 61-79,
1988.
\label{pa-R6} \end{paper}
Within this approach the drawing is incrementally specified in three
phases (see Fig.~\ref{fi-t}): The first phase, {\em planarization},
determines the topology of the drawing. The second phase, {\em
orthogonalization}, computes an orthogonal shape for the drawing. The
third phase, {\em compaction}, produces the final drawing. This
approach allows homogeneous treatment of a wide range of diagrammatic
representations, aesthetics and constraints.
 
Another approach to the construction of orthogonal grid drawings,
based on the results of [\ref{pa-XJ}] and on visibility representations
(Section~\ref{se-visibility}), is presented in:
 
\begin{paper}
H.\ de Fraysseix and P.\ Rosenstiehl, ``Structures Combinatoires
pour des Traces Automatiques de Reseaux,'' Proc.\ 3rd European
Conf.\ on CAD/CAM and Computer Graphics, Paris, pp.\ 332-337,
Hermes, 1984.
\label{pa-YD} \end{paper}
 
An algorithm for constructing polyline grid drawings that allows the
user to choose between a hierarchical drawing method and the
orthogonal grid drawing technique of [\ref{pa-R6}] is presented in.
 
\begin{paper}
H.\ Trickey, ``Drag: A Graph Drawing System,'' Proc.\ Int.\ Conf.\ on
Electronic Publishing, pp.\ 171-182, Cambridge University
Press, 1988.
\label{pa-WS} \end{paper}
 
Orthogonal grid drawings of graphs whose vertices have preassigned
locations in the plane are investigated in:
 
\begin{paper}
Y.\ Kajitani and H.\ Takahashi, ``Rectilinear Drawing of a Graph on
a Plane with the Minimum Number of Segments,'' Manuscript
(presented at the 2nd Int.\ Catania Combinatorial Conf.),
1989.
\label{pa-UG} \end{paper}
 
\iffig \begin{figure}[htb] %  t 5.0in
\centering\ostrategy
\caption{A general strategy for orthogonal grid drawings. (a)~Given
graph. (b)~Planarization. (c)~Orthogonalization. (d)~Compaction.}
\label{fi-t}
\end{figure} \fi
 

% -------------------------------------------------------------------

\section{Planar Graphs} \label{se-planar}
 
A graph is {\em planar} if it admits a planar drawing. Planar graphs
play an important role in graph theory [\ref{pa-RA}, \ref{pa-RB}] and
graph algorithms; see [\ref{pa-RC}, \ref{pa-ZY}], and:
 
\begin{paper}
R.E.\ Tarjan, ``Algorithm Design,'' Communications ACM, vol.\ 30, no.
3, pp.\ 205-212, 1987.
\label{pa-XH} \end{paper}
 
Clearly, planar drawings are aesthetically desirable. Furthermore, as
discussed in the previous section, algorithms for drawing nonplanar
graphs often begin by {\em planarizing} the graph (see
section~\ref{se-planarization}), and then by applying a planar graph
drawing algorithm.

\subsection{Planarity Testing and Planar Representations} \label{se-planartest}
 
A {\em planar representation} is a data structure representing the
combinatorial adjacencies between the faces of a planar drawing.  Most
planar graph drawing methods proceed as follows:
\begin{enumerate}
\item [] {\em Step 1.} Test planarity.
\item [] {\em Step 2.} (if the graph is planar) Construct a planar representation.
\item [] {\em Step 3.} Use the planar representation to draw the                  graph according to some graphic standard.
\end{enumerate}
In this subsection we consider the first two steps.
 
Finding a linear time algorithm to test the planarity of a graph
was an interesting challenge for early algorithms research.
The first algorithm to succeed used a {\em path addition approach} and
was presented in:
 
\begin{paper}
J.\ Hopcroft and R.E.\ Tarjan, ``Efficient Planarity Testing,'' J.
ACM, vol.\ 21, no.\ 4, pp.\ 549-568, 1974.
\label{pa-XI} \end{paper}
 
Minor errors of~[\ref{pa-XI}] are corrected in:
 
\begin{paper}
N.\ Deo, ``Note on Hopcroft and Tarjan's Planarity Algorithm,''
J.\ ACM, vol.\ 23, no.\ 1, pp.\ 74-75, 1976.
\label{pa-P23} \end{paper}
 
The {\em vertex addition approach} was developed to give a linear
time algorithm in the following papers:
 
\begin{paper}
A.\ Lempel, S.\ Even, and I.\ Cederbaum, ``An Algorithm for Planarity
Testing of Graphs,'' in Theory of Graphs, Int.\ Symposium
(Rome, 1966), pp.\ 215-232, Gordon and Breach, New York,
1967.
\label{pa-UB} \end{paper}
 
\begin{paper}
S.\ Even and R.E.\ Tarjan, ``Computing an st-Numbering,'' Theoretical
Computer Science, vol.\ 2, pp.\ 339-344, 1976.
\label{pa-UC} \end{paper}
 
\begin{paper}
K.\ Booth and G.\ Lueker, ``Testing for the Consecutive Ones
Property, Interval Graphs, and Graph Planarity Using PQ-Tree
Algorithms,'' J.\ of Computer and System Sciences, vol.\ 13,
pp.\ 335-379, 1976.
\label{pa-RD} \end{paper}
 
Another approach is presented in:
 
\begin{paper}
H.\ de Fraysseix and P.\ Rosenstiehl, ``A Depth-First-Search
Characterization of Planarity,'' Annals of Discrete
Mathematics, vol.\ 13, pp.\ 75-80, 1982.
\label{pa-XJ} \end{paper}
 
The aforementioned planarity testing algorithms can be modified to
construct planar representations. The following
paper extends the algorithm of [\ref{pa-RD}] in this way.
 
\begin{paper}
N.\ Chiba, T.\ Nishizeki, S.\ Abe, and T.\ Ozawa, ``A Linear Algorithm
for Embedding Planar Graphs Using PQ-Trees,'' J.\ of Computer
and System Sciences, vol.\ 30, no.\ 1, pp.\ 54-76, 1985.
\label{pa-XK} \end{paper}
 
In the remainder of this Section we consider drawing algorithms that
construct a planar drawing from a given planar representation.
 
% -------------------------------------------------------------------
 
\subsection{Straight-Line Drawings}
 
A classical result independently established by Wagner, Fary and Stein
shows that every planar graph admits a planar straight-line drawing.
 
\begin{paper}
K.\ Wagner, ``Bemerkungen zum Vierfarbenproblem,'' Jber.\ Deutsch.
Math.-Verein, vol.\ 46, pp.\ 26-32, 1936.
\label{pa-XL} \end{paper}
 
\begin{paper}
I.\ Fary, ``On Straight Lines Representation of Planar Graphs,''
Acta Sci.\ Math.\ Szeged, vol.\ 11, pp.\ 229-233, 1948.
\label{pa-XM} \end{paper}
 
\begin{paper}
S.K.\ Stein, ``Convex Maps,'' Proc.\ Amer.\ Math.\ Soc., vol.\ 2, pp.
464-466, 1951.
\label{pa-XN} \end{paper}
 
This result also follows from Steinitz's theorem on convex polytopes
in three dimensions.
 
\begin{paper}
E.\ Steinitz and H.\ Rademacher, Vorlesung \"uber die Theorie der
Polyeder, Springer, Berlin, 1934.
\label{pa-WT} \end{paper}
 
{\em Convex drawings} of planar graphs, that is, planar straight-line
drawings where every face is drawn as a convex polygon (see
Fig.~\ref{fi-f}) were first studied by Tutte.
 
\begin{paper}
W.T.\ Tutte, ``Convex Representations of Graphs,'' Proc.\ London Math
Soc., vol.\ 10, pp.\ 304-320, 1960.
\label{pa-XO} \end{paper}
 
\begin{paper}
W.T.\ Tutte, ``How to Draw a Graph,'' Proc.\ London Math Soc., vol.
3, no.\ 13, pp.\ 743-768, 1963.
\label{pa-XP} \end{paper}
 
\iffig \begin{figure}[hbt] %  f 2.75in
\centering\convex
\caption{Convex drawing.}
\label{fi-f}
\end{figure} \fi
 
Tutte shows that a convex drawing of a {\em 3-connected graph} (see
[\ref{pa-RA}]) can be obtained by solving a system of linear equations.
Thomassen characterizes the class of graphs that admit a convex
drawing.
 
\begin{paper}
C.\ Thomassen, ``Planarity and Duality of Finite and Infinite
Planar Graphs,'' J.\ Combinatorial Theory, Series B, vol.\ 29,
pp.\ 244-271, 1980.
\label{pa-XQ} \end{paper}

Chiba et al.\ show that Thomassen's result can be implemented as an
algorithm for producing a convex drawing in linear time.
 
\begin{paper}
N.\ Chiba, T.\ Yamanouchi, and T.\ Nishizeki, ``Linear Algorithms for
Convex Drawings of Planar Graphs,'' in Progress in Graph
Theory, ed.\ J.A.\ Bondy and U.S.R.\ Murty, pp.\ 153-173,
Academic Press, 1984.
\label{pa-XR} \end{paper}
 
\begin{paper}
N.\ Chiba, K.\ Onoguchi, and T.\ Nishizeki, ``Drawing Planar Graphs
Nicely,'' Acta Informatica, vol.\ 22, pp.\ 187-201, 1985.
\label{pa-XS} \end{paper}
 
Becker et al.\ investigate the problem of minimizing the total edge
length (according to several metrics, not including the Euclidean
metric) in a planar straight-line drawing where the external face is a
prescribed convex polygon.  They show that the optimal drawing is
unique and convex, and can be obtained by standard numerical
techniques.

\begin{paper}
B.\ Becker and G.\ Hotz, ``On The Optimal Layout of Planar Graphs
with Fixed Boundary,'' SIAM J.\ Computing, vol.\ 16, no.\ 5, pp.
946-972, 1987.
\label{pa-XT} \end{paper}
 
\begin{paper}
B.\ Becker and H.G.\ Osthof, ``Layout with Wires of Balanced
Length,'' Information and Computation, vol.\ 73, pp.\ 45-58,
1987.
\label{pa-XU} \end{paper}
 
Eades and Wormald show that the problem of constructing a planar
straight-line drawing with prescribed edge lengths (according to the
Euclidean metric) is NP-hard.
 
\begin{paper}
P.\ Eades and N.\ Wormald, ``Fixed Edge Length Graph Drawing is NP-
hard,'' Discrete Applied Mathematics, vol. 28, pp. 111-134, 1990.
\label{pa-XW} \end{paper}
 
An elegant algorithm for constructing planar straight-line drawings has
been given by Read. The algorithm uses $O(n)$ time but $O(n^2)$
storage.
 
\begin{paper}
R.\ Read, ``New Methods for Drawing a Planar Graph Given the Cyclic
Order of the Edges at Each Vertex,'' Congressus Numerantium,
vol.\ 56, pp.\ 31-44, 1987.
\label{pa-XV} \end{paper}

Manning and Atallah give algorithms for and discuss complexity
of displaying symmetries in
planar straight-line drawings of planar graphs in [\ref{pa-XG}]
and:

\begin{paper}
    J. Manning and M. Atallah.  ``Fast Detection and Display of
    Symmetry in Outerplanar Graphs,'' Discrete Applied Mathematics vol.
    39 no. 1 pp.\ 13--35 (1992).
\label{pa-XX}
\end{paper}

\begin{paper}
M.J.\ Atallah and J.\ Manning, ``Fast Detection and Display of Symmetry
in Embedded Planar Graphs,'' Manuscript, Purdue Univ., 1988.
\label{pa-RX} \end{paper}

\begin{paper}
    J. Manning, ``Computational Complexity of Geometric Symmetry
    Detection in Graphs,'' Lecture Notes in Computer Science vol. 507
    pp. 1--7 Springer-Verlag, June 1991.
\label{pa-MA1}
\end{paper}

\begin{paper}
    J. Manning.  ``Geometric Symmetry in Graphs,'' Ph.D. Thesis,
    Department of Computer Sciences, Purdue University, Dec 1990.
\label{pa-MA2}
\end{paper}

Schnyder and de Fraysseix et al.\  independently show that every planar
graph admits a planar straight-line grid drawing with area $O( n^2)$.
 
\begin{paper}
H.\ de Fraysseix, J.\ Pach, and R.\ Pollack, ``Small Sets Supporting
Fary Embeddings of Planar Graphs,'' Proc.\ 20th ACM Symp.\ on
Theory of Computing, pp.\ 426-433, 1988.
\label{pa-XY} \end{paper}
 
\begin{paper}
H.\ de Fraysseix, J.\ Pach, and R.\ Pollack, ``How to Draw a Planar
Graph on a Grid,'' Combinatorica, vol.\ 10, pp.\ 41-51, 1990.
\label{pa-P19} \end{paper}
 
\begin{paper}
W.\ Schnyder, ``Embedding Planar Graphs on the Grid,'' Proc.\ ACM-
SIAM Symp.\ on Discrete Algorithms, pp.\ 138-148, 1990.
\label{pa-WK} \end{paper}

Chrobak and Payne show that the constructive proof of [\ref{pa-XY}] can be
modified to yield an $O(n)$-time drawing algorithm.

\begin{paper}
M.\ Chrobak and T.H.\ Payne, ``A Linear Time Algorithm for Drawing a
Planar Graph on a Grid,'' Technical Report UCR-CS-90-2, Dept.\ of
Math.\ and Comput.\ Sci., Univ.\ California, Riverside, 1990.
\label{pa-WA} \end{paper}

The performance of the algorithms in [\ref{pa-XR}], [\ref{pa-WA}],
[\ref{pa-XV}], and [\ref{pa-XP}] are compared in the following paper.
These algorithms have been implemented and tested on randomly generated
maximal planar graphs.  The standard deviations in angle size, edge
length, and face area are used to compare the quality of the planar
straight-line drawings produced.

\begin{paper}
S.\ Jones, P.\ Eades, A.\ Moran, N.\ Ward, G.\ Delott, and R.\ Tamassia,
``A Note on Planar Graph Drawing Algorithms,''
Technical Report 216, Dept.\ of Computer Science, Univ.\ of
Queensland, 1991.
\label{pa-P27} \end{paper}
 
Kant presents an algorithm for constructing planar convex straight-line
grid drawings with area $O(n^2)$.  His technique has several other graph
drawing applications.

\begin{paper}
G.\ Kant, ``Algorithms for Drawing Planar Graphs,''
Ph.D.\ Thesis, Utrecht University, 1993.
\label{pa-KA1} \end{paper}
 
\begin{paper}
G.\ Kant, ``Drawing Planar Graphs Using the {\it lmc}-Ordering,''
Proc.\ IEEE Symp.\ on Foundations of Computer Science, pp.
101-110, 1992.
\label{pa-P34} \end{paper}
 
Several of the algorithms that produce planar straight-line drawings operate
primarily on triangulations.  Thus for this and other applications,
algorithms for triangulating planar graphs are required.
Such algorithms are presented in:
 
\begin{paper}
G.\ Kant and H.L.\ Bodlaender, ``Triangulating Planar Graphs while
Minimizing the Maximum Degree,'' in Algorithm Theory (SWAT '92),
(Proc.\ 3rd Scandinavian Workshop on Algorithm Theory, Helsinki, July
1992), ed.\ O.\ Nurmi E.\ Ukkonen, pp.\ 258-271, Lecture Notes in
Computer Science, vol.\ 621, Springer-Verlag, 1992.
\label{pa-P3} \end{paper}
 
% -------------------------------------------------------------------
 
\subsection{Orthogonal Grid Drawings}
 
Investigations of planar orthogonal grid drawings were first motivated
by problems in circuit layout. Within this graphic standard, minimizing
the number of bends and the area is important for both diagram
readability and VLSI applications (see Fig.~\ref{fi-g}).
 
Any planar graph of degree at most 4 admits a planar orthogonal grid
drawing with area $O(n^2)$. Further, there are graphs which need
quadratic area. These results are presented in:
 
\begin{paper}
Y.\ Shiloach, ``Arrangements of Planar Graphs on the Planar
Lattice,'' Ph.D.\ Thesis, Weizmann Institute of Science,
Rehovot, Israel, 1976.
\label{pa-UE} \end{paper}
 
\begin{paper}
L.\ Valiant, ``Universality Considerations in VLSI Circuits,'' IEEE
Transactions on Computers, vol.\ C-30, no.\ 2, pp.\ 135-140,
1981.
\label{pa-YA} \end{paper}

The problem of testing whether a graph admits a planar orthogonal
drawing with no bends is NP-complete, as shown in:

\begin{paper}
A.\ Garg and R.\ Tamassia, ``On the Computational Complexity of Upward
and Rectilinear Planarity Testing,'' Technical Report CS-94-10,
Dept.\ of Computer Science, Brown Univ., 1994.
\label{pa-GT94} \end{paper}

Hence, the corresponding bend-minimization probelm is NP-hard.
 
Tamassia uses network flow techniques to give an $O( n^2 \log n)$-time
algorithm for minimizing bends in a fixed embedding setting.

\begin{paper}
R.\ Tamassia, ``On Embedding a Graph in the Grid with the Minimum
Number of Bends,'' SIAM J.\ Computing, vol.\ 16, no.\ 3, pp.
421-444, 1987.
\label{pa-XZ} \end{paper}

Di~Battista, Liotta, and Vargiu give polynomial time algorithms for
minimizing bends (considering all the possible embeddings) for
series-parallel graphs and graphs with degree at most 3.

\begin{paper}
G.\ Di~Battista, G.\ Liotta, and F.\ Vargiu, ``Spirality of Orthogonal
Representations and Optimal Drawings of Series-Parallel Graphs and
$3$-Planar Graphs,'' Proc.\ WADS'93, LNCS 709, pp.\ 15--162, 1993.
\label{pa-PXX1}
\end{paper}

\iffig \begin{figure}[hbt] %  g 3.4in
\centering\areabend
\caption{Examples of planar orthogonal grid drawings.}
\label{fi-g}
\end{figure} \fi
 
Storer gives three heuristics for constructing drawings with $O(n)$
bends.

\begin{paper}
J.A.\ Storer, ``On Minimal Node-Cost Planar Embeddings,'' Networks,
vol.\ 14, pp.\ 181-212, 1984.
\label{pa-R1} \end{paper}

Tamassia and Tollis present another heuristic for bend minimization
which has the same performance bounds as the ones by Storer and runs
in $O(n)$ time.
 
\begin{paper}
R.\ Tamassia and I.G.\ Tollis, ``Efficient Embedding of Planar
Graphs in Linear Time,'' Proc.\ IEEE Int.\ Symp.\ on Circuits
and Systems, pp.\ 495-498, Philadelphia, 1987.
\label{pa-RH} \end{paper}
 
\begin{paper}
R.\ Tamassia and I.G.\ Tollis, ``Planar Grid Embedding in Linear
Time,'' IEEE Trans.\ on Circuits and Systems, vol.\ CAS-36, no.
9, pp.\ 1230-1234, 1989.
\label{pa-WB} \end{paper}

The structure of orthogonal embeddings of graphs is investigated in:
 
\begin{paper}
G. Vijayan and A. Wigderson. ``Rectilinear Graphs and their Embeddings,''
SIAM Journal on Computing, vol.\ 14, no.\ 2, pp.\ 355-372, May 1985.
\label{pa-VW85} \end{paper}

Lower bounds for planar orthogonal drawings of graphs, and parallel
algorithms for achieving the same performance bounds  as the ones by
Storer and Tamassia and Tollis are described in

\begin{paper}
R.\ Tamassia, I.G.\ Tollis, and J.S.\ Vitter, ``Lower Bounds for Planar
Orthogonal Drawings of Graphs,'' {\em Information Processing Letters},
vol.~39, pp.~35-40 (1991).
\label{pa-TTV91} \end{paper}

\begin{paper}
R.\ Tamassia, I.G.\ Tollis, and J.S.\ Vitter, ``Lower Bounds and
Parallel Algorithms for Planar Orthogonal Grid Drawings,'' Proc.\ IEEE
Symposium on Parallel and Distributed Processing, pp.~386-393 (1991).
\label{pa-TTV291} \end{paper}

NP-completeness results related to the minimization of area and total
edge length in planar orthogonal grid drawings have been presented in
[\ref{pa-WC}, \ref{pa-RM}, \ref{pa-R1}, \ref{pa-PDE6}, \ref{pa-PDE7}]
and:
 
\begin{paper}
D.\ Dolev, F.T.\ Leighton, and H.\ Trickey, ``Planar Embedding of
Planar Graphs,'' in Advances in Computing Research, vol.\ 2,
ed.\ F.P.\ Preparata, pp.\ 147-161, JAI Press Inc., Greenwich,
CT, 1984.
\label{pa-YB} \end{paper}

This paper also gives a heuristic for area minimization.
 
Orthogonal drawing algorithms are briefly surveyed in:
 
\begin{paper}
R.\ Tamassia, ``Planar Orthogonal Drawings of Graphs,'' Proc.\ IEEE
Int.\ Symp.\ on Circuits and Systems, 1990.
\label{pa-P4} \end{paper}

% -------------------------------------------------------------------
 
\subsection{Visibility Representations} \label{se-visibility}
 
A {\em visibility representation} for a planar graph $G$ consists of
representing the vertices of $G$ by horizontal segments, and the edges
of $G$ by vertical segments, so that the edge-segment associated with
each edge $(u,v)$ intersects exactly the vertex-segments associated
with $u$ and $v$, and no other vertex-segment (see Fig.~\ref{fi-h}).
 
\iffig \begin{figure}[hbt] %  h 2.75in
\centering\visibility
\caption{Visibility representation for the graph of
Fig.~\protect{\ref{fi-g}}.}
\label{fi-h} \end{figure} \fi
 
The study of this graphic standard was originally motivated by VLSI
layout and compaction problems because it gives regular and modular
drawings.
 
\begin{paper}
M.\ Schlag, F.\ Luccio, P.\ Maestrini, D.T.\ Lee, and C.K.\ Wong, ``A
Visibility Problem in VLSI Layout Compaction,'' in Advances
in Computing Research, vol.\ 2, ed.\ F.P.\ Preparata, pp.\ 259-
282, JAI Press Inc., Greenwich, CT, 1985.
\label{pa-YC} \end{paper}
 
Theoretical results characterizing visibility representations and
variations of it appear in:
 
\begin{paper}
P.\ Duchet, Y.\ Hamidoune, M.\ Las Vergnas, and H.\ Meyniel,
``Representing a Planar Graph by Vertical Lines Joining
Different Levels,'' Discrete Mathematics, vol.\ 46, pp.\ 319-
321, 1983.
\label{pa-YE} \end{paper}
 
\begin{paper}
C.\ Thomassen, ``Plane Representations of Graphs,'' in Progress in
Graph Theory, ed.\ J.A.\ Bondy and U.S.R.\ Murty, pp.\ 43-69,
Academic Press, 1984.
\label{pa-YF} \end{paper}
 
\begin{paper}
S.K.\ Wismath, ``Characterizing Bar Line-of-Sight Graphs,'' Proc.
ACM Symp.\ on Computational Geometry, pp.\ 147-152, 1985.
\label{pa-YG} \end{paper}

\begin{paper}
R.\ Tamassia and I.G.\ Tollis, ``Centipede Graphs and Visibility on
a Cylinder,'' in Graph-Theoretic Concepts in Computer
Science, (Proc.\ Int.\ Workshop WG '86, Bernierd, June 1986),
ed.\ G.\ Tinhofer and G.\ Schmidt, pp.\ 252-263, Lecture Notes
in Computer Science, vol.\ 246, Springer-Verlag, 1987. 
\label{pa-TT87} \end{paper}

\begin{paper}
R.\ Tamassia and I.G.\ Tollis, ``Representations of Graphs on a
Cylinder,`` SIAM J.\ on Discrete Mathematics, vol.\ 4, no.\ 1,
pp.\ 139-149, 1991.
\label{pa-YH} \end{paper}
 
\begin{paper}
F.\ Luccio, S.\ Mazzone, and C.\ Wong, ``A Note on Visibility
Graphs,'' Discrete Mathematics, vol.\ 64, pp.\ 209-219, 1987.
\label{pa-YI} \end{paper}
 
\begin{paper}
D.G. Kirkpatrick and S.K.\ Wismath, ``Weighted Visibility Graphs of Bars and Related
Flow Problems,'' Algorithms and Data Structures (Proc.
WADS'89), pp.\ 325-334, Lecture Notes in Computer Science,
vol.\ 382, Springer-Verlag, 1989.
\label{pa-SQ} \end{paper}

\begin{paper}
T.\ Andreae, ``Some Results on Visibility Graphs,''
Discrete Applied Mathematics, vol.\ 40, pp.\ 5-17, 1992.
\label{pa-Andreae92} \end{paper}

Algorithms that construct visibility representations in linear time
are given in the following papers and in~[\ref{pa-YL}].
 
\begin{paper}
R.H.J.M.\ Otten and J.G.\ van Wijk, ``Graph Representations in
Interactive Layout Design,'' Proc.\ IEEE Int.\ Symp.\ on
Circuits and Systems, pp.\ 914-918, New York, 1978.
\label{pa-YJ} \end{paper}
 
\begin{paper}
P.\ Rosenstiehl and R.E.\ Tarjan, ``Rectilinear Planar Layouts and
Bipolar Orientations of Planar Graphs,'' Discrete \& Computational
Geometry, vol.\ 1, no.\ 4, pp.\ 343-353, 1986.
\label{pa-YK} \end{paper}

\begin{paper}
J. Nummenmaa, Constructing compact rectilinear planar layouts using
canonical representation of planar graphs, Theoretical Computer 
Science 99 (1992), pp.\ 213-230.
\label{pa-N92} \end{paper}

\begin{paper}
G.\ Kant, ``A More Compact Visibility Representation,''
Proc.\ Int.\ Workshop on Graph-Theoretic Concepts in Computer Science
(WG '93), Lecture Notes in Computer Science, 1993.
\label{pa-Kant} \end{paper}

A complete combinatorial characterization of three classes of
visibility representations and linear time drawing algorithms are
presented in:
 
\begin{paper}
R.\ Tamassia and I.G.\ Tollis, ``A Unified Approach to Visibility
Representations of Planar Graphs,'' Discrete \& Computational
Geometry, vol.\ 1, no.\ 4, pp.\ 321-341, 1986.
\label{pa-YL} \end{paper}
 
An algorithm to construct {\em constrained} visibility representations
(that is, representations where the edges of given paths are aligned)
is presented in:
 
\begin{paper}
G.\ Di Battista, R.\ Tamassia, and I.G.\ Tollis, ``Constrained Visibility
Representations of Graphs,'' Information Processing Letters, vol.\ 41,
pp.\ 1-7, 1992.
\label{pa-P5} \end{paper}

Linear-time algorithms for constructing visibility representations of
trees with optimal area are presented in:

\begin{paper}
G.\ Kant, G.\ Liotta, R.\ Tamassia, and I.G.\ Tollis,
``Area Requirement of Visibility Representations of Trees,''
Proc. 1993 Canadian Conference on Computational Geometry,
Waterloo, Ontario, Aug. 1993, pp.\ 192-197.
\label{pa-KLTT93} \end{paper}
 
A {\em bipolar orientation} of an undirected graph consists of
orienting the edges so that the resulting directed graph is acyclic and
has exactly one source (vertex without incoming edges) and exactly one
sink (vertex without outgoing edges).  The creation of a bipolar
orientation is often the first step for the generation of a visibility
representation.  The properties of bipolar orientations are
systematically explored in terms of circuits, cocircuits, rank
activities, Tutte polynomial, poset dimension, angle bipartition and
max flow-min cut theorem in:

\begin{paper}
H.\ de Fraysseix, P.O.\ de Mendez, and P.\ Rosenstiehl, ``Bipolar
Orientations revisited,'' Technical Report P089, Centre d'Analyse et de
Mathematique Sociales, Ecole des Hautes Etudes en Sciences Sociales,
Paris, 1993.  (Preliminary version in Proc. Fifth Franco-Japanese Days
on Combinatorics and Optimization, 1992.)
\label{pa-P24} \end{paper}

Efficient algorithms are described to list, generate or extend bipolar
orientations for general graphs or plane ones, with or without
constraints. The importance of the paper goes beyond visibility
representations; in fact bipolar orientations are exploited in several
drawing algorithms.

% -------------------------------------------------------------------
 
\subsection{Other Graphic Standards}
 
Algorithms for constructing planar polyline grid drawings are
described in [\ref{pa-UE}] and:
 
\begin{paper}
A.K.\ Hope, ``A Planar Graph Drawing Program,'' Software Practice
and Experience, vol.\ 1, pp.\ 83-91, 1971.
\label{pa-R8} \end{paper}
 
\begin{paper}
D.\ Woods, ``Drawing Planar Graphs,'' Ph.D.\ dissertation (Technical
Report STAN-CS-82-943), Computer Science Dept., Stanford
Univ., 1982.
\label{pa-RI} \end{paper}
 
Another standard is proposed by Ozawa:  vertices are placed on a
horizontal line and edges are drawn as half-circles or smooth
connections of half-circles.

\begin{paper}
T.\ Ozawa, ``Planarity Testing for IC Layout with Constraints for
Pin Order and Congestion Between Pins,'' IEEE Conf.\ Record of
the 14th Asilomar Conf.\ on Circuits, Systems  Computers, pp.
188-192, 1980.
\label{pa-YM} \end{paper}
 
Kant investigates representations of planar cubic graphs in the
hexagonal grid, presenting a linear time algorithm:

\begin{paper}
G.\ Kant, ``Hexagonal Grid Drawings,'' Technical Report RUU-CS-92-06,
Department of Computer Science, Utrecht Univ., The Netherlands, 1992.
\label{pa-P6} \end{paper}
 
Representations of planar graphs by means of subdivisions of the plane
into polygons (usually rectangles) have been motivated by problems in
architectural design. Each vertex is represented by a polygon, and for
each edge $(u,v)$ the polygons associated with vertices $u$ and $v$ are
geometrically adjacent. Essentially, this amounts to representing the
graph by its dual. In most cases, the polygons are required to be
rectangles; linear time algorithms for finding such dual
representations are presented in:
 
\begin{paper}
J.\ Bhasker and S.\ Sahni, ``A Linear Algorithm to Find a
Rectangular Dual of a Planar Triangulated Graph,''
Algorithmica, vol.\ 3, no.\ 2, pp.\ 247-278, 1988.
\label{pa-QW} \end{paper}
 
\begin{paper}
X. \ He, ``On Finding the Rectangular Duals of Planar Triangulated
Graphs,'' SIAM J.\ Computing (to appear).  Technical Report 90-24,
Department of Computer Science, University of Buffalo 1990.
\label{pa-PDEa} \end{paper}

\begin{paper}
G.\ Kant and X. \ He, ``Two Algorithms for Finding Rectangular Duals of
Planar Graphs,'' Proc.\ Int.\ Workshop on Graph-Theoretic Concepts in
Computer Science (WG '93), Lecture Notes in Computer Science, 1993.
\label{pa-KantHe} \end{paper}

Background to the architectural motivation can be found in:
 
\begin{paper}
J.P.\ Steadman, Architectural Morphology, Pion, London, 1983.
\label{pa-YN} \end{paper}
 
In a {\em tessellation representation}, each constituent (vertex,
edge, and face) of an embedded planar graph is represented by a
rectangle with horizontal and vertical sides, and incidencies between
constituents correspond to geometric adjacencies between rectangles
(see Fig.~\ref{fi-w}). These representations are investigated in:
 
\begin{paper}
R.\ Tamassia and I.G.\ Tollis, ``Tessellation Representations of
Planar Graphs,'' Proc.\ 27th Annual Allerton Conf., pp.\ 48-57,
1989.
\label{pa-SR} \end{paper}
 
\iffig \begin{figure}[hbt] %  w  4.0in
\centering\tessellation
\caption{(a)~A planar graph $G$.  (b)~Tessellation representation for
$G$.}
\label{fi-w}
\end{figure} \fi
 
An algorithm that maps vertices to grid points to facilitate the
construction of a planar drawing is described in:
 
\begin{paper}
R.\ Jayakumar, K.\ Thulasiraman, and M.N.S Swamy, ``Planar
Embedding: Linear-Time Algorithms for Vertex Placement and
Edge Ordering,'' IEEE Trans.\ on Circuits and Systems, vol.
35, no.\ 3, pp.\ 334-344, 1988.
\label{pa-Y3} \end{paper}
 

% -------------------------------------------------------------------
 
\section{Directed Graphs} \label{se-digraphs}
 
\subsection{Acyclic Digraphs} \label{se-dags}
 
Acyclic digraphs are widely used to display hierarchical structures.
Examples include PERT diagrams, ISA hierarchies, and various dependency
graphs. It is customary to represent these graphs so that the edges all
flow in the same direction, e.g., from top to bottom, or from left to
right (see Fig.~\ref{fi-l}). Namely, we say that a drawing of a digraph
is {\em upward} if each arc is a curve monotonically increasing in the
$y$-direction.
 
An important class of acyclic digraphs are covering digraphs of
partially ordered sets. These digraphs are commonly represented by
upward straight-line drawings, called {\em order diagrams}, {\em Hasse
diagrams}, or simply {\em diagrams}.

A drawing algorithm for order diagrams is described in:
 
\begin{paper}
H.~J\"urgensen and J.~Loewer: Drawing Hasse diagrams of partially
ordered sets. In: G.~Kalmbach, Orthomodular lattices.
Academic Press, London, 1983, pp.\ 331--345.
\label{pa-R9} \end{paper}
 
Several issues in drawing order diagrams, such as the minimization of
the number of slopes used for the arcs, are investigated in:
 
\begin{paper}
I.\ Rival and R.\ Wille, ``Lattices Freely Generated by Partially
Ordered Sets: Which can be Drawn?,'' J.\ f\"ur Reine und Angew.
Math., vol.\ 310, pp.\ 56-80, 1979.
\label{pa-SY} \end{paper}
 
\begin{paper}
J.\ Czyzowicz, A.\ Pelc, and I.\ Rival, ``Drawing Orders with Few
Slopes,'' Technical Report TR-87-12, Dept.\ of Computer
Science, Univ.\ of Ottawa, 1987.
\label{pa-YR} \end{paper}
 
\begin{paper}
J.\ Czyzowicz, A.\ Pelc, I.\ Rival, and J.\ Urrutia, ``Crooked
Diagrams with Few Slopes,'' Technical Report TR-87-26, Dept.
of Computer Science, Univ.\ of Ottawa, 1987.
\label{pa-YS} \end{paper}
 
\begin{paper}
A.\ Pelc and I.\ Rival, ``Orders with Level Diagrams,'' Technical
Report TR-87-11, Dept.\ of Computer Science, Univ.\ of Ottawa,
March 1987.
\label{pa-YT} \end{paper}
 
\begin{paper}
J.\ Czyzowicz, ``Lattice Diagrams with Few Slopes,'' Technical
Report \#3, D\'epartement D'Informatique, Univ.\ of Quebec at
Hull, 1987.
\label{pa-YU} \end{paper}
 
\begin{paper}
J.\ Czyzowicz, ``Planar Lattices and the Slope Problem,'' Technical
Report \#4, D\'epartement D'Informatique, Univ.\ of Quebec at
Hull, 1987.
\label{pa-Y9} \end{paper}
 
\begin{paper}
J.\ Czyzowicz, A.\ Pelc, and I.\ Rival, ``Planar Ordered Sets of
Width Two,'' Technical Report TR-87-31, Dept.\ of Computer
Science, Univ.\ of Ottawa, 1987.
\label{pa-SZ} \end{paper}
 
Surveys on drawing techniques for order diagrams appear in:
 
\begin{paper}
I.\ Rival, ``The Diagram,'' in Graphs and Orders, ed.\ I.\ Rival, pp.
103-133, Reidel Publishing, 1985.
\label{pa-SX} \end{paper}
 
\begin{paper}
I.\ Rival, ``Graphical Data Structures for Ordered Sets,'' in
Algorithms and Order, ed.\ I.\ Rival, pp.\ 3-31, Kluwer Academic
Publishers, 1989.
\label{pa-RL} \end{paper}

\begin{paper}
I.\ Rival, ``Reading, Drawing, and Order,'' in Algebras and Orders,
eds.\ I.G. Rosenberg and G. Sabidussi, pp.\ 359-404, Kluwer Academic
Publishers, 1993.
\label{pa-rival93} \end{paper}

 
\subsubsection{Upward Planarity}
 
\iffig \begin{figure}[htb] %  l 2.7in
\centering\upward
\caption{ Planar upward drawing of an acyclic digraph.}
\label{fi-l}
\end{figure} \fi
 
The notion of planarity of undirected graphs has a corresponding notion
of ``upward planarity'' for directed graphs. A digraph is said to be
{\em upward planar} if it admits a planar upward drawing (see Fig.
\ref{fi-l}).  Note that an upward planar graph must be acyclic and its
underlying undirected graph must be planar; however, there are planar
acyclic digraphs which are not upward planar:  see Fig. \ref{fi-PDEb}.
 
\iffig \begin{figure}[hbt] %  l 2.7in
\centering\nonupward
\caption{Planar acyclic digraph which is not upward planar.}
\label{fi-PDEb}
\end{figure} \fi
 
Various combinatorial characterizations of upward planarity
are presented in:
 
\begin{paper}
D.\ Kelly and I.\ Rival, ``Planar Lattices,'' Canadian J.
Mathematics, vol.\ 27, no.\ 3, pp.\ 636-665, 1975.
\label{pa-YP} \end{paper}
 
\begin{paper}
C.\ Platt, ``Planar Lattices and Planar Graphs,'' J.\ Combinatorial
Theory, Series B, vol.\ 21, pp.\ 30-39, 1976.
\label{pa-YQ} \end{paper}
 
\begin{paper}
D.\ Kelly, ``Fundamentals of Planar Ordered Sets,'' Discrete
Mathematics, vol.\ 63, pp.\ 197-216, 1987.
\label{pa-RE} \end{paper}
 
\begin{paper}
G.\ Di~Battista and R.\ Tamassia, ``Algorithms for Plane
Representations of Acyclic Digraphs,'' Theoretical Computer Science,
vol.\ 61, pp.\ 175-198, 1988.
\label{pa-RF} \end{paper}
 
\begin{paper}
C.\ Thomassen, ``Planar Acyclic Oriented Graphs,'' Order, vol.\ 5,
no.\ 4, pp.\ 349-361, 1989.
\label{pa-SU} \end{paper}

The problem of testing whether a digraph is upward planar is
NP-complete, as shown in~[\ref{pa-GT94}]. For special classes of graphs,
polynomial time algorithms have been found.  These appear in:
 
\begin{paper}
G.\ Di Battista, W.P.\ Liu, and I.\ Rival, ``Bipartite Graphs, Upward
Drawings, and Planarity,'' Information Processing Letters, vol.\ 36,
pp.\ 317-322, 1990.
\label{pa-P14} \end{paper}
 
\begin{paper}
M.D.\ Hutton and A.\ Lubiw, ``Upward Planar Drawing of Single Source
Acyclic Digraphs,'' Proc.\ 2nd ACM-SIAM Symp.\ on Discrete Algorithms,
pp.\ 203-211, 1991.
\label{pa-P15} \end{paper}
 
\begin{paper}
P.\ Bertolazzi and G.\ Di~Battista, ``On Upward Drawing Testing of
Triconnected Digraphs,'' Proc.\ 7th ACM Symp.\ on Computational
Geometry, pp.\ 272-280, 1991.
\label{pa-P16} \end{paper}
 
\begin{paper}
P.\ Bertolazzi, G.\ Di~Battista, G.\ Liotta, and C.\ Mannino ``Upward
Drawings of Triconnected Digraphs,'' Algorithmica (to appear).
\label{pa-P42} \end{paper}

\begin{paper}
P.\ Bertolazzi, G.\ Di~Battista, C.\ Mannino, and R.\ Tamassia,
``Optimal Upward Planarity Testing of Single-Source Digraphs,''
Proc.\ European Symp.\ on Algorithms, 1993.
\label{pa-esa} \end{paper}

Planarization-based algorithms for upward drawings have three steps
corresponding to the three phases for drawing general graphs as
described in Subsection~\ref{se-polyline}.

If the topological structure (that is, a planar representation) of an
upward planar digraph is known, then an upward drawing may be
efficiently obtained; algorithms are given in~[\ref{pa-RF}].
For a survey see:

\begin{paper}
R.\ Tamassia, ``Drawing Algorithms for Planar st-Graphs,'' {\em
Australasian Journal of Combinatorics}, vol.~2, pp.~217-235 (1990).
\label{pa-TAJC90} \end{paper}

In contrast to undirected graphs, upward planar straight line grid
drawings may require exponential area. These results, as well as a
discussion of symmetry display, may be found in:
 
\begin{paper}
G.\ Di~Battista, R.\ Tamassia, and I.G.\ Tollis, ``Area Requirement
and Symmetry Display in Drawing Graphs,'' Proc.\ ACM Symp.\ on
Computational Geometry, pp.\ 51-60, 1989.
\label{pa-YV} \end{paper}
 
\begin{paper}
G.\ Di~Battista, R.\ Tamassia, and I.G.\ Tollis, ``Area Requirement
and Symmetry Display of Planar Upward Drawings,'' Discrete \&
Computational Geometry, vol.\ 7, pp.\ 381-401, 1992.
\label{pa-P17} \end{paper}

Lower bounds on area requirements and algorithms for constructing
planar upward drawings of series-parallel digraphs are given in:

\begin{paper}
P.\ Bertolazzi, R.F.\ Cohen, G.\ Di~Battista, R.\ Tamassia, and
I.G.\ Tollis, ``How to Draw a Series-Parallel Digraph,'' in Algorithm
Theory (SWAT '92), (Proc.\ 3rd Scandinavian Workshop on Algorithm Theory,
Helsinki, July 1992), ed.\ O.\ Nurmi E.\ Ukkonen, pp.\ 272-283, Lecture
Notes in Computer Science, vol.\ 621, Springer-Verlag, 1992.
\label{pa-P18} \end{paper}

\begin{paper}
P.\ Bertolazzi, R.F.\ Cohen, G.\ Di~Battista, R.\ Tamassia, and
I.G.\ Tollis, ``How to Draw a Series-Parallel Digraph,'' International
Journal of Computational Geometry \& Applications (to appear).
\label{pa-BCDTT94} \end{paper}
 
\subsubsection{Hierarchical Drawings}
 
A {\em hierarchical} drawing of an acyclic digraph is an upward
polyline drawing where the vertices and bends are constrained to lie
on a set of equally spaced horizontal lines, called {\em layers} (see
Fig.~\ref{fi-d}). In some applications the assignment of vertices to
layers is given, e.g., by the semantics of the graph. Such graphs are
called {\em layered digraphs}, or {\em hierarchies}.
 
\iffig \begin{figure}[hb] %  d 2.7in
\centering\hierarchy
\caption{Hierarchical drawing.}
\label{fi-d}
\end{figure} \fi
 
Most of the rooted tree drawing algorithms of Section~\ref{se-trees}
may be used to draw trees as hierarchies.
Sugiyama et al.\ present a comprehensive approach
(see Fig.~\ref{fi-x}):
 
\begin{description}
 
\item[] {\em Step~1} Assign vertices to the layers so that arcs
are directed upward and vertices are
distributed uniformly.
 
\item[] {\em Step~2} Select a permutation of the vertices in each layer to
reduce crossings.
 
\item[] {\em Step~3} Adjust the position of the vertices in each layer to
reduce the number of bends.
 
\end{description}
  
\begin{paper}
K.\ Sugiyama, S.\ Tagawa, and M.\ Toda, ``Methods for Visual
Understanding of Hierarchical Systems,'' IEEE Trans.\ on
Systems, Man, and Cybernetics, vol.\ SMC-11, no.\ 2, pp.\ 109-
125, 1981.
 
\label{pa-R3} \end{paper}
 
\begin{paper}
K.\ Sugiyama and M.\ Toda, ``Structuring Information for
Understanding Complex Systems: A Basis for Decision Making,''
FUJITSU Scientific and Technical Journal, vol.\ 21, no.\ 2,
pp.\ 144-164, 1985.
\label{pa-YZ} \end{paper}
 
\begin{paper}
K.\ Sugiyama, ``A Cognitive Approach for Graph Drawing,''
Cybernetics and Systems: An International Journal, vol.\ 18,
pp.\ 447-488, 1987.
 
\label{pa-WF} \end{paper}
 
Variations and extensions of this approach are presented in:
 
\begin{paper}
M.J.\ Carpano, ``Automatic Display of Hierarchized Graphs for
Computer Aided Decision Analysis,'' IEEE Trans.\ on Systems,
Man, and Cybernetics, vol.\ SMC-10, no.\ 11, pp.\ 705-715,
1980.
 
\label{pa-R2} \end{paper}
 
\begin{paper}
M.J.\ Carpano and M.\ Delarche, ``Apport des Techniques Graphiques
Interactives \'a l'Analyse Structurale de Syst\`emes.\ II-
Exemples de Realization et d'Application,'' RAIRO Sept.\ Anal.
Cont., June 1980.
\label{pa-ZA} \end{paper}
 
\begin{paper}
M.\ May and P.\ Mennecke, ``Layout of Schematic Drawings,'' Syst.
Anal.\ Model.\ Simul., vol.\ 1, 4, pp.\ 307-338, 1984.
\label{pa-P35} \end{paper}
 
\begin{paper}
L.A.\ Rowe, M.\ Davis, E.\ Messinger, C.\ Meyer, C.\ Spirakis, and A.
Tuan, ``A Browser for Directed Graphs,'' Software Practice and
Experience, vol.\ 17, no.\ 1, pp.\ 61-76, 1987.
\label{pa-R4} \end{paper}
 
\begin{paper}
E.B.\ Messinger, ``Automatic Layout of Large Directed Graphs,''
Technical Report 88-07-08, Univ.\ of Washington, Dept.\ of
Computer Science, 1988.
 
\label{pa-RT} \end{paper}
 
\begin{paper}
E.R.\ Gansner, S.C.\ North, and K.P.\ Vo, ``DAG -- A Program that
Draws Directed Graphs,'' Software Practice and Experience, vol.
18, no.\ 11, pp.\ 1047-1062, 1988.
\label{pa-SJ} \end{paper}
 
\begin{paper}
D.\ Jablonowski and V.A.\ Guarna, ``GMB: A Tool for Manipulating and
Animating Graph Data Structures,'' Software Practice and
Experience, vol.\ 19, no.\ 3, pp.\ 283-301, 1989.
\label{pa-SF} \end{paper}
 
\begin{paper}
E.R.\ Gansner, E.\ Koutsofios, S.C.\ North, and K.P.\ Vo,
``A Technique for Drawing Directed Graphs,''
IEEE Trans.\ on Software Engineering, vol.\ 19, no.\ 3, pp.\ 214-230, 1993.
\label{pa-P40} \end{paper}
 
\iffig \begin{figure}[hbt] %  x 5.0in
\centering\hstrategy
\caption{A general strategy for hierarchical drawings. (a)~Given digraph.
(b)~Assignment of vertices to layers. (c)~Crossing reduction.
(d)~Placement of vertices and bends.}
\label{fi-x}
\end{figure} \fi
 
Analyses of algorithms used at each of the three steps
are presented in:
 
\begin{paper}
P.\ Eades and X.\ Lin, ``How to Draw a Directed Graph,'' Proc.\ IEEE
Workshop on Visual Languages (VL'89), pp.\ 13-17, 1989.
\label{pa-QJ} \end{paper}
 
\begin{paper}
P.\ Eades and K.\ Sugiyama, ``How to Draw a Directed Graph,'' Journal
of Information Processing, vol.\ 14, no.\ 4, pp.\ 424--437, 1990.
\label{pa-PDEd} \end{paper}
 
\begin{paper}
P. Eades, ``Complexity Issues in Drawing Directed Graphs,''
Proc.\ Int.\ Workshop on Discrete Algorithms and Complexity, pp. 9--15,
Fukuoka, Japan, 1989.
\label{pa-PDEe}
\end{paper}
 
\begin{paper}
X. Lin,
``Analysis of Algorithms for Drawing Graphs,''
PhD thesis,
Department of Computer Science,
University of Queensland,
1992.
\label{pa-PDEf}
\end{paper}
 
Heuristics for the assignment of vertices to layers in Step~1
of the above technique are described in:
 
\begin{paper}
K.\ Sugiyama, ``A Readability Requirement on Drawing Digraphs:
Level Assignment and Edge Removal for Reducing the Total
Length of Lines,'' Research Report no.\ 45, Int.\ Inst.\ for
Advanced Study of Social Information Science, FUJITSU,
Numazu, Japan, March 1984.
\label{pa-ZB} \end{paper}
 
\begin{paper}
P.\ Eades and X.\ Lin,, ``Notes on the Layer Assignment Problem for
Drawing Directed Graphs,'' ACSC 14, Proc.\ 14th Australian
Computer Science Conference, University of New South Wales, pp. 26-10,
1991.
\label{pa-PDEg}
\end{paper}
 
A divide-and-conquer algorithm for hierarchical drawings is proposed
in:
 
\begin{paper}
E.B.\ Messinger, L.A.\ Rowe, and R.H.\ Henry, ``A Divide-and-Conquer
Algorithm for the Automatic Layout of Large Directed Graphs,'' IEEE
Trans. on Systems, Man, and Cybernetics, vol.\ SMC-21, no.\ 1, pp.
1-12, 1991. 
\label{pa-UF} \end{paper}
 
A recursive algorithm for hierarchical drawings that partitions the
original graph into subgraphs whose elements are closely related is
presented in:
 
\begin{paper}
D.J.\ Gschwind and T.P.\ Murtagh, ``A Recursive Algorithm for Drawing
Hierarchical Directed Graphs,'' Technical Report CS-89-02, Dept.\ of
Computer Science, Williams College, 1989.
 
\label{pa-SV} \end{paper}
 
A linear time algorithm for constructing hierarchical drawings is
presented in:
 
\begin{paper}
G.\ Robins, ``The ISI Grapher: A Portable Tool for Displaying
Graphs Pictorially,'' Technical Report ISI/RS-87-196,
Information Sciences Inst., Univ.\ of Southern California,
1987.\  (Also in Proc.\ Symboliikka '87, Helsinki, Finland,
August 1987)
 
\label{pa-WO} \end{paper}
 
Orthogonal hierarchical drawings are investigated in:
 
\begin{paper}
J.E.\ Savage, ``Heuristics for Level Graph Embeddings,'' Proc.
Workshop on Graphtheoretic Concepts in Computer Science, pp.
307-318, Trauner Verlag, 1983.
 
\label{pa-QU} \end{paper}
 
Crossing reduction is a fundamental aesthetic for hierarchical
drawings. An efficient algorithm to construct a planar hierarchical
drawing of a layered digraph is given in:
 
\begin{paper}
G.\ Di~Battista and E.\ Nardelli, ``An Algorithm for Testing Planarity
of Hierarchical Graphs,'' in Graph-Theoretic Concepts in Computer
Science, (Proc.\ Int.\ Workshop WG '86, Bernierd, June 1986),
ed.\ G.\ Tinhofer and G.\ Schmidt, pp.  277-289, Lecture Notes in
Computer Science, vol.\ 246, Springer-Verlag, 1987.
\label{pa-ZC} \end{paper}
 
\begin{paper}
G.\ Di~Battista and E.\ Nardelli, ``Hierarchies and Planarity
Theory,'' IEEE Trans.\ on Systems, Man, and Cybernetics, 1988.
\label{pa-WE} \end{paper}
 
An algorithm which uses a technique adapted from [\ref{pa-XP}]
for hierarchical drawings is presented in:

\begin{paper}
P. Eades, X. \ Lin and R. \ Tamassia,
An Algorithm for Drawing a Hierarchical Graph,
Proc.\ Second Canadian Conference on Computational Geometry,
(edit. J. Urrutia)
University of Ottawa, 1990,
142-146.
\label{pa-PDEh}
\end{paper}

Minimizing crossings for layered digraphs is NP-hard even if there are
only two layers [\ref{pa-ZL}], and even if there is only one
node in each layer:

\begin{paper}
S. Masuda, K. Nakajima, T. Kashiwabara and T. Fujisawa,
Crossing Minimization in Linear Embeddings of Graphs,
IEEE Transactions on Computers,
vol. 39, no. 1 (1990), pp 124 - 127.
\label{pa-MNKF90} \end{paper}

Further NP-completeness results, as well as
analyses of an heuristics (one of which gives at most three
times the minimum number of crossings) are given in:

\begin{paper}
P.\ Eades, B.\ McKay, and N.\ Wormald, ``On an Edge Crossing Problem,''
Proc.\ 9th Australian Computer Science Conf., pp.  327-334, Australian
National University, 1986.
\label{pa-ZD} \end{paper}

\begin{paper}
P.\ Eades and N.\ Wormald, ``Edge Crossings in Drawings of Bipartite
Graphs'' Technical Report 108, Department of Computer Science,
University od Queensland.  (to appear in Algorithmica).
\label{pa-PDEi} \end{paper}

Other heuristics for crossing minimization in layered digraphs are
studied in the following papers:
 
\begin{paper}
J.\ Warfield, ``Crossing Theory and Hierarchy Mapping,'' IEEE Trans.
on Systems, Man, and Cybernetics, vol.\ SMC-7, no.\ 7, pp.
502-523, 1977.
\label{pa-ZF} \end{paper}
 
\begin{paper}
P.\ Eades and D.\ Kelly, ``Heuristics for Drawing 2-
Layered Networks,'' Ars Combinatoria, vol.\ 21.A, pp.\ 89-98,
1986.
\label{pa-ZG} \end{paper}
 
\begin{paper}
E.\ M\"akinen, ``Experiments on Drawing 2-Level Hierarchical Graphs,''
International Journal of Computer Mathematics 36 (1990), 175-181.
\label{pa-ZH} \end{paper}
 
\begin{paper}
E.\ M\"akinen, ``A Note on the Median Heuristic for Drawing Bipartite
Graphs,'' Fundamenta Informaticae XII (1989), 563-570.
\label{pa-WD} \end{paper}
 
\begin{paper}
T.\ Catarci, ``The Assignment Heuristic for Crossing Reduction in
Bipartite Graphs,'' Proc.\ 26th Annual Allerton Conf., 1988.
% XXX PAGE NUMBERS????
\label{pa-WH} \end{paper}
 
\begin{paper}
M.\ May and K.\ Szkatula, ``On the Bipartite Crossing
Number,'' Control and Cybernetics, vol.\ 17, no.\ 1, pp.\ 85-98,
1988.
\label{pa-P31} \end{paper}
 
\begin{paper}
E.\ M\"akinen, ``Remarks on the Assignment Heuristic for Drawing
Bipartite Graphs,'' Technical Report A-1990-7, Dept.\ of Computer
Science, Univ.\ of Tampere, Finland, 1990.
\label{pa-P29} \end{paper}
 
\begin{paper}
E.\ M\"akinen, ``On Drawing Regular Bipartite Graphs,'' International
Journal of Computer Mathematics 43 (1992), 39-43.
\label{pa-P30} \end{paper}
 
A heuristic algorithm that simplifies dense hierarchical graphs
by replacing complete bipartite subgraphs with
a single ``concentrator node'' is presented in the following paper.
 
\begin{paper}
F.J.\ Newbery, ``Edge Concentration: A Method for Clustering
Directed Graphs,'' Proc.\ 2nd Int.\ Workshop on Software Configuration
Management, pp.\ 76-85, 1989.
\label{pa-P32} \end{paper}
The transformation greatly enhances visual simplicity
and may reduce the number of crossings;
see [\ref{pa-PDEf}] for a discussion of the complexity
issues involved.
 
The display of symmetries in hierarchical drawings is investigated in
[\ref{pa-PDEh}] and:
 
\begin{paper}
K.\ Sugiyama, ``Achieving Uniqueness Requirement in Drawing
Digraphs: Optimum Code Algorithm and Hierarchic
Isomorphism,'' Research Report no.\ 58, Int.\ Inst.\ for
Advanced Study of Social Information Science, FUJITSU,
Numazu, Japan, July 1985.
 
\label{pa-ZI} \end{paper}
 
Radial drawings of layered digraphs are investigated in [\ref{pa-R2}] and:
 
\begin{paper}
M.G.\ Reggiani and F.E.\ Marchetti, ``A Proposed Method for
Representing Hierarchies,'' IEEE Trans.\ on Systems, Man, and
Cybernetics, vol.\ 18, no.\ 1, pp.\ 2-8, 1988.
 
\label{pa-QY} \end{paper}

\subsubsection{Dominance Drawings}

A {\em dominance drawing} of an acyclic directed graph $G = (V, E)$ is
a function $f : V \leftarrow R^k$ such that $(f(u), f(v)) \in E$ if and
only if $f(u) \neq f(v)$ and each coordinate of $f(v)$ is at least as
large as the corresponding coordinate of $f(u)$. A dominance drawing in
dimension $k$ can be viewed as an embedding of the graph in a $k$
dimensional partial order.  Thus several mathematical results on
partial orders can be used to derive algorithms for dominance
drawings.  Algorithms and complexity of creating such representations
are given in~[\ref{pa-P17}] and:

\begin{paper}
T. Kameda,
On the vector representation of the reachability
in planar directed graphs,
Information Processing Letters, vol. 3, no. 3 (1975) pp. 75-77.
\label{pa-DOM1}
\end{paper}

\begin{paper}
A.\ Pnueli, A.\ Lempel, and S.\ Even, ``Transitive orientation of graphs
and identification of permutation graphs,'' Canad. J. Math., 23 (1971)
pp. 160-175.
\label{pa-DOM2}
\end{paper}

\begin{paper}
M. Yannakakis,
``The complexity of the partial order dimension problem,'' SIAM J. Alg.
and Disc. Meth., vol. 3, no. 3 (1982) pp. 351-358.
\label{pa-DOM3}
\end{paper}

Related results appear in [\ref{pa-YP}] and [\ref{pa-RE}].

Algorithms for dominance drawings of series parallel graphs are in
[\ref{pa-P18}].  A linear time algorithm for finding a dominance
drawing of a bipartite graph in two dimensions is given in

\begin{paper}
P. Eades, H. ElGindy, M. Houle, W. Lenhart, M. Miller,
D. Rappaport and S. Whitesides, ``Dominance Drawings of Bipartite
Graphs,'' manuscript 1993.
\label{pa-DOM4}
\end{paper}

% -------------------------------------------------------------------
 
\subsection{General Digraph Drawing Algorithms}
 
When the representation of {\em flow} in digraphs with cycles is an
important aesthetic, one would like to maximize the number of arcs that
are directed upward. This problem is equivalent to reversing a minimum
number of arcs to make the digraph acyclic, and is commonly known as
the {\em feedback arc set problem}.  The problem is NP-complete in
general, but it is polynomially solvable for several classes of graphs
including planar digraphs:
 
\begin{paper}
A. Frank, ``How to Make a Digraph Strongly Connected,'' {\em
Combinatorica}, vol. 1, no. 2, 1981.
\label{pa-PDEl} \end{paper}
 
Heuristics for the feedback arc set problem are discussed in
[\ref{pa-R3}, \ref{pa-R2}, \ref{pa-R4}, \ref{pa-RT}, \ref{pa-SJ},
\ref{pa-SF}, \ref{pa-ZB}, \ref{pa-UF}, \ref{pa-SV}, \ref{pa-QJ},
\ref{pa-PDEf}], and
 
\begin{paper}
B. Berger and P. Shor, ``Approximation Algorithms for the Maximum
Acyclic Subgraph Problem,'' Proc.\ ACM-SIAM Symposium on Discrete
Algorithms (1990), pp. 236-243.
\label{pa-PDEm}
\end{paper}

After the transformation into an acyclic digraph, the techniques
surveyed in the previous subsection can be applied.

If the representation of flow is not important, algorithms for drawing
undirected graphs can be applied by ignoring the directions of the
arcs.
 
% -------------------------------------------------------------------
 
\subsection{Application-Specific Algorithms}
 
There are several drawing algorithms developed for specific
applications, especially circuit schematics and software engineering
diagrams. In this framework, the semantics of the diagram and the
conventions of the application area may put constraints on the
drawing.  For example, vertices representing interfaces in a Data Flow
diagram are conventionally placed on the external boundary.  In this
section we list a sample of papers covering such application specific
techniques.

The problem of dealing with constraints on the drawing imposed by the
user is specifically investigated in:
 
\begin{paper}
R.\ Tamassia, ``New Layout Techniques for Entity-Relationship
Diagrams,'' Proc.\ 4th Int.\ Conf.\ on Entity-Relationship
Approach, pp.\ 304-311, Chicago, 1985.
\label{pa-QC} \end{paper}
 
The automatic generation of schematic diagrams for digital systems is
studied in:
 
\begin{paper}
A.\ Arya, A.\ Kumar, V.\ Swaminathan, and A.\ Misra, ``Automatic
Generation of Digital System Schematic Diagrams,'' Proc.\ 22nd
Design Automation Conf., pp.\ 388-395, 1985.
\label{pa-QD} \end{paper}
 
\begin{paper}
F.\ Aoudja, M.\ Laborie, and A.\ Saint-Paul, ``CASE: Automatic
Generation of Electrical Diagrams,'' Computer-Aided Design,
vol.\ 18, no.\ 7, pp.\ 356-360, 1986.
\label{pa-RK} \end{paper}
 
\begin{paper}
M.A.\ Majewski, F.N.\ Krull, T.E.\ Fuhrman, and P.J.\ Ainslie,
``Autodraft: Automatic Synthesis of Circuit Schematics,''
Proc.\ IEEE Int.\ Conf.\ on Computer-Aided Design, pp.\ 435-438,
1986.
\label{pa-SI} \end{paper}

Following the classical layout approach for integrated circuits, these
algorithms perform the placement of modules and the routing of
connections in two separate steps.
 
A drawing algorithm for PERT diagrams is presented in:
 
\begin{paper}
G.\ Di~Battista, E.\ Pietrosanti, R.\ Tamassia, and I.G.\ Tollis,
``Automatic Layout of PERT Diagrams with XPERT,'' Proc.\ IEEE
Workshop on Visual Languages (VL'89), pp.\ 171-176, 1989.
\label{pa-SS} \end{paper}
 
An algorithm for drawing flowcharts appears in:
 
\begin{paper}
D.E.\ Knuth, ``Computer Drawn Flocharts,'' Communications of the
ACM, vol.\ 6, 1963.
\label{pa-SN} \end{paper}
 
The following papers describe divide-and-conquer algorithms targeted
toward Entity Relationship diagrams:
 
\begin{paper}
D.\ Reiner, M.\ Brodie, G.\ Brown, M.\ Chilenskas, M.\ Friedell, D.
Kramlich, J.\ Lehman, and A.\ Rosenthal, ``A Database Design
and Evaluation Workbench: Preliminary Report,'' Proc.\ Int.
Conf.\ on Systems Development and Requirements Specification,
Gothenburg, Sweden, 1984.
\label{pa-RJ} \end{paper}
 
\begin{paper}
D.\ Reiner, G.\ Brown, M.\ Friedell, J.\ Lehman, R.\ McKee, P.
Rheingans, and A.\ Rosenthal, ``A Database Designer's
Workbench,'' in Entity-Relationship Approach (Proc.\ 5th Int.
Conf.\ on Entity-Relationship Approach, Dijon, France, 1987),
ed.\ S.\ Spaccapietra, pp.\ 347-360, North-Holland, 1987.
\label{pa-R5} \end{paper}
 
\begin{paper}
D.\ Reiner and G.\ Brown, ``Heuristic Layout for DDEW ER+ Diagrams,''
Manuscript, Computer Corporation of America, 1985.
\label{pa-QE} \end{paper}
 
An algorithm for Entity Relationship diagrams based on visibility
representations is in:
 
\begin{paper}
J.\ Nummenmaa and J.\ Tuomi, ``Constructing Layouts for ER-Diagrams
from Visibility Representations,'' Proc.\ 9th Int.\ Conf.\ on
Entity-Relationship Approach, pp.\ 303-317, Lausanne, Switzerland,
1990.
\label{pa-P9} \end{paper}
 
Based on the general strategy of [\ref{pa-QB}, \ref{pa-R6}], drawing
algorithms for three diagrammatic representations widely used in
databases and software engineering are given in:
 
\begin{paper}
C.\ Batini, M.\ Talamo, and R.\ Tamassia, ``Computer Aided Layout of
Entity-Relationship Diagrams,'' The Journal of Systems and
Software, vol.\ 4, pp.\ 163-173, 1984.
\label{pa-QF} \end{paper}
 
\begin{paper}
P.\ Di Felice and R.\ Tamassia, ``Automatic Layout of Flow Diagrams:
Preliminary Analysis,'' Proc.\ ISMM, pp.\ 263-267, Madrid,
1985.
\label{pa-QG} \end{paper}
 
\begin{paper}
C.\ Batini, E.\ Nardelli, and R.\ Tamassia, ``A Layout Algorithm for
Data-Flow Diagrams,'' IEEE Transactions on Software
Engineering, vol.\ SE-12, no.\ 4, pp.\ 538-546, 1986.
\label{pa-QH} \end{paper}
 
Layout methods for class hierarchies used in object-oriented systems
are developed in:
 
\begin{paper}
H.\ Koike, ``An Application of Three Dimensional Visualization to
Object-Oriented Programming,'' {\em Advanced Visual Interfaces}
(Proc.\ AVI'92), World Scientific Series in Computer Science
vol.\ 36, 180-192.
\label{pa-PDEs} \end{paper}
 
 
% -------------------------------------------------------------------
 
\section{Graph Drawing Systems} \label{se-systems}
 
There are many computer systems available for editing graphs and
graph-like diagrams. Some of these contain a simple automatic drawing
facility:
 
\begin{paper}
M.\ Dao, M.\ Habib, J.\ Richard, and D.\ Tallot, ``CABRI, an
Interactive System for Graph Manipulation,'' in Graph-
Theoretic Concepts in Computer Science, (Proc.\ Int.\ Workshop
WG '86, Bernierd, June 1986), ed.\ G.\ Tinhofer and G.
Schmidt, pp.\ 58-67, Lecture Notes in Computer Science, vol.
246, Springer-Verlag, 1987.
\label{pa-QI} \end{paper}
 
\begin{paper}
J.M Fourneau, I.\ Fournier, A.\ Germa, and D.\ Sotteau, ``Unicorn: A
Computer-Aided Scratch Book for Graph Theory,'' Technical
Report 381, L.R.I., UA410 CNRS, Univ.\ Paris Sud, 1987.
\label{pa-WR} \end{paper}
 
\begin{paper}
F.\ Aschim and B.M.\ Mostue, ``IFIP WG 8.1 Case Solved Using SYSDOC
and SYSTEMATOR,'' in Information Systems Design
Methodologies: a Comparative Review (Proc.\ of the IFIP WG
8.1 Working Conf.\ on Comparative Review of Information
Systems Design Methodologies), ed.\ T.\ Olle et al., pp.\ 15-
40, North-Holland, Noordwijkerhout, the Netherlands, 1982.
\label{pa-QL} \end{paper}
 
\begin{paper}
M.\ Nagl and H.\ Zischler, ``A Dialog System for the Graphical
Representation of Graphs,'' Applied Computer Science, vol.\ 13
(Proc.\ Workshop WG '78 on Graphtheoretic Concepts in
Computer Science), pp.\ 325-339, 1979.
\label{pa-QM} \end{paper}
 
\begin{paper}
M.\ Sarkar and M.H.\ Brown, ``Graphical Fisheye Views of Graphs,''
Technical Report CS-91-61, Dept.\ of Computer Science, Brown Univ.,
1991.
\label{pa-SB91} \end{paper}
 
Other systems use significant layout algorithms. They are described
in [\ref{pa-SG}, \ref{pa-R8}, \ref{pa-RI}, \ref{pa-R9}, \ref{pa-R3},
\ref{pa-YZ}, \ref{pa-R2}, \ref{pa-R4}, \ref{pa-SJ}, \ref{pa-SF},
\ref{pa-R7}, \ref{pa-UA}, \ref{pa-QZ}, \ref{pa-R6}, \ref{pa-RK},
\ref{pa-SI}, \ref{pa-SS}, \ref{pa-RJ}, \ref{pa-R5}] and:
 
\begin{paper}
M.\ Himsolt, ``GraphEd: An Interactive Graph Editor,'' Proc.\ STACS
89, Lecture Notes in Computer Science, vol.\ 349, pp.\ 532-
533, Springer-Verlag, 1989.
\label{pa-RV} \end{paper}

\begin{paper}
J.\ Hynd and P.\ Eades, ``The Typed Graph Editing System - TYGES,''
Proc.\ 3rd Australasian Conf.\ on Computer Graphics (Ausgraph
85), pp.\ 15-19, Brisbane, Australia, 1985.
\label{pa-QN} \end{paper}
 
\begin{paper}
P.\ Eades, I.\ Fogg and D.\ Kelly,
``SPREMB: a System for Developing Graph Algorithms''.
Congressus Numerantium vol. 66 (1988), 123-140.
\label{pa-QO} \end{paper}
 
\begin{paper}
C.\ Batini, E.\ Nardelli, M.\ Talamo, and R.\ Tamassia, ``GINCOD: a
Graphical Tool for Conceptual Design of Data Base
Applications,'' in Computer Aided Data Base Design, ed.\ A.
Albano, V.\ De Antonellis, and A.\ Di Leva, pp.\ 33-51, North
Holland, 1985.
\label{pa-QP} \end{paper}
 
\begin{paper}
G.\ Di~Battista and R.\ Tamassia, ``An Integrated Graphic System for
Designing and Accessing Statistical Data Bases,'' Proc.\ 7th
Symp.\ on Computational Statistics (COMPSTAT 1986), pp.\ 231-
236, Physica-Verlag, 1986.
\label{pa-QQ} \end{paper}
 
\begin{paper}
C.\ Batini, P.\ Brunetti, G.\ Di~Battista, P.\ Naggar, E.\ Nardelli,
G.\ Richelli, and R.\ Tamassia, ``An Automatic Layout Facility
and its Applications,'' Proc.\ Int.\ Workshop on Software
Engineering Environment, pp.\ 139-157, China Academic
Publishers, Beijing, China, 1986.\  (invited paper)
\label{pa-QR} \end{paper}
 
\begin{paper}
R.\ Read, ``Methods for Computer Display and Manipulation of
Graphs, and the Corresponding Algorithms,'' Research Report
CORR 86-12, Faculty of Mathematics, Univ.\ of Waterloo, July
1986.
\label{pa-QS} \end{paper}
 
\begin{paper}
K.\ Nakamura, H.\ Fujimoto, T.\ Suzuki, Y.\ Tarui, and Y.\ Kiyokane,
``Visual Programming Environment in Communications Software,''
Proc.\ 5th IEEE Global Telecom Conf., pp.\ 435-439, 1986.
\label{pa-SW} \end{paper}
 
\begin{paper}
W.F.\ Tichy and F.J.\ Newbery, ``Knowledge-based Editors for
Directed Graphs,'' in ESEC'87 (Proc.\ 1st European Software
Engineering Conf.), ed.\ H.K.\ Nichols and D.\ Simpson, pp.
109-117, Springer-Verlag, 1987.
\label{pa-QT} \end{paper}
 
\begin{paper}
G.\ Kar, B.P.\ Madden, and R.S.\ Gilbert, ``Heuristic Layout Algorithms  
for Network Management Presentation Services,'' IEEE Network, (November,  
1988), pp.\ 29-36.
\label{pa-KMG88} \end{paper}

\begin{paper}
F.\ Newbery, ``An Interface Description Language for Graph
Editors,'' Proc.\ IEEE Workshop on Visual Languages, 1988.
\label{pa-WM} \end{paper}
 
\begin{paper}
F. Newberry Paulisch and W.F. Tichy: ``EDGE: An Extendible Graph Editor,''
Software-Practice and Experience, vol. 20, no. S1, pp. 63-88,
1990
\label{pa-WN} \end{paper}
 
\begin{paper}
S.P.\ Reiss and J.N.\ Pato, ``Displaying Program and Data
Structures,'' Proc.\ 20th Hawaii Int.\ Conf.\ on System
Sciences, 1987.
\label{pa-WU} \end{paper}
 
\begin{paper}
S.P.\ Reiss, ``Integration Mechanisms in the FIELD Environment,''
Technical Report CS-88-18, Dept.\ of Computer Science, Brown
Univ., 1988.
\label{pa-WV} \end{paper}
 
\begin{paper}
S.P.\ Reiss, S.\ Meyers, and C.\ Duby, ``Interacting with the FIELD
Environment,'' Technical Report CS-89-51, Dept.\ of Computer Science,
Brown Univ., 1989.
\label{pa-SH} \end{paper}
 
\begin{paper}
B.\ Birgisson and G.\ Shannon, ``GraphView: A Workstation-Based
Environment for Viewing Graphs and Animating Graph
Algorithms,'' Technical Report 295, Dept.\ Computer Science,
Indiana Univ., 1989.
\label{pa-UD} \end{paper}
 
\begin{paper}
V.\ Jansen, A.\ Potthoff, W.\ Thomas, and U.\ Wermuth, ``A Short Guide
to the AMORE System,'' Technical Report 90-2,  Fachgruppe Informatik,
RWTH Aachen, 1990.
\label{pa-P26} \end{paper}

\begin{paper}
O.\ Baudon, ``Cabri-graphes, un CAhier de BRouillon Interactif
pour la theorie des graphes,'' These de Doctorat de l'Universite Joseph
Fourier, Grenoble, France, 1990.
\label{pa-Baudon}
\end{paper}

\begin{paper}
J.\ Bordier and J.M.\ Laborde, ``An Interactive Tool for Graph Theory,''
Proc.\ 7th Annual Apple European University Consortium Conference,
Paris, France, ed. Apple Computer Europe, Inc, pp.\ 51-53, 1991.
\label{pa-Bordier}
\end{paper}

\begin{paper}
G.\ Di~Battista, G.\ Liotta, M.\ Strani and F.\ Vargiu, ``Diagram
Server,'' {\em Advanced Visual Interfaces} (Proc.\ AVI 92),
World Scientific Series in Computer Science, vol.\ 36, pp.\ 415-417, 1992.
\label{pa-PDEt} \end{paper}
 
\begin{paper}
G.\ Di~Battista, A.\ Giammarco, G.\ Santucci, and R.\ Tamassia,
``The Architecture of Diagram Server,'' Proc.\ IEEE
Workshop on Visual Languages (VL'90), pp.\ 60-65, 1990.
\label{pa-P10} \end{paper}
 
\begin{paper}
M.\ Beccaria, P.\ Bertolazzi, G.\ Di~Battista, and G.\ Liotta,
``A Tailorable and Extensible Automatic Layout Facility,'' Proc.\ IEEE
Workshop on Visual Languages (VL'91), pp.\ 68-73, 1991.
\label{pa-P11} \end{paper}
 
\begin{paper}
M.\ Bousset and P.\ Rosenstiehl, ``Twist,'' Tech.\ Rep.\ CAMS P.073,
1991.
\label{pa-P41} \end{paper}
 
\begin{paper}
J.C.\ Smart and V.\ Vemuri, ``A-Vu: A Visualization Tool for Complex
Software Systems'' Proc.\ Symposium on Assessment of Quality Software
Development Tools, IEEE Computer Society Press, New Orleans LA, May
27-29, 1992.
\label{pa-P45} \end{paper}
 
\begin{paper}
E.R.\ Gansner, E.\ Koutsofios, S.C.\ North, and K.P.\ Vo,
``Graph Visualization in Software Analysis''
Proc.\ Symposium on Assessment of Quality Software Development
Tools, IEEE Computer Society Press, New Orleans LA, May 27-29, 1992. 
\label{pa-P46} \end{paper}

\begin{paper}
S.\ Skiena, ``Implementing Discrete Mathematics,'' Addison
Wesley, 1990.
\label{pa-Skiena} \end{paper}

A graph drawing system for dataflow diagrams based on placement-and-routing
techniques is described in:
 
\begin{paper}
L.B.\ Protsko, P.G.\ Sorenson, J.P.\ Tremblay, and D.A.\ Schaefer,
``Towards the Automatic Generation of Software Diagrams,''IEEE
Trans.\ on Software Engineering, vol.\ SE-17, no.\ 1, pp.\ 10-21,
1991.
\label{pa-P8} \end{paper}
 
A tool for displaying large graphs supporting multiple views,
nonuniform scaling, and user-defined constraints on the layout is
described in:
 
\begin{paper}
T.R.\ Henry and S.E.\ Hudson, ``Viewing Large Graphs,'' Technical
Report 90-13, Dept.\ of Computer Science, Univ.\ of Arizona, 1990.
\label{pa-P33} \end{paper}
 
A tool that uses clustering techniques is described in:
 
\begin{paper}
P.\ Brown, T.\ Gargiulo, ``An Object Oriented Layout for Directed
Graphs,'' Proc.\ Symposium on Assessment of Quality Software
Development Tools, IEEE Computer Society Press, New Orleans LA, May
27-29, 1992.
\label{pa-P44} \end{paper}


% -------------------------------------------------------------------
 
\section{Special Topics} \label{se-other}

\subsection{Parallel Algorithms}
 
A parallel algorithm for planarity testing that runs in $O(\log n)$ time
on a CRCW PRAM with $(n \log\log n)/\log n$ processors is presented in:
 
\begin{paper}
V.\ Ramachandran and J.H.\ Reif, ``An Optimal Parallel Algorithm for
Graph Planarity,'' Proc.\ IEEE Symp.\ on Foundations of
Computer Science, pp.\ 282-293, 1989.
\label{pa-WP} \end{paper}
 
\begin{paper}
V.\ Ramachandran and J.\ Reif, ``Planarity Testing in Parallel,''
Technical Report TR-90-15, Dept.\ of Computer Science, The University
of Texas at Austin, 1990.
\label{pa-P36} \end{paper}
 
Previous results on parallel planarity testing are:
 
\begin{paper}
J.\ Ja'Ja' and J.\ Simon, ``Parallel Algorithms in Graph Theory:
Planarity Testing,'' SIAM J.\ Comput., vol.\ 11, no.\ 2, pp.
314-328, 1982.
\label{pa-P37} \end{paper}
 
\begin{paper}
G.L.\ Miller and J.H.\ Reif, ``Parallel Tree Contraction and its
Applications,'' Proc.\ 26th IEEE Symp.\ on Foundations of Computer
Science, pp.\ 478-489, 1985.
\label{pa-P38} \end{paper}
 
\begin{paper}
P.N.\ Klein and J.H.\ Reif, ``An Efficient Parallel Algorithm for
Planarity,'' J.\ Computer and System Sciences, vol.\ 37, no.\ 2,
pp.\ 190-246, 1988.
\label{pa-P39} \end{paper}

Parallel graph drawing algorithms for planar graphs are presented in 
[\ref{pa-TTV291}] and in the following papers:
 
\begin{paper}
R.\ Tamassia and J.S.\ Vitter, ``Optimal Parallel Algorithms for
Transitive Closure and Point Location in Planar Structures,'' Proc.
ACM Symp.\ on Parallel Algorithms and Architectures, pp.~399-408
(1989).
\label{pa-TV89} \end{paper}

\begin{paper}
R.\ Tamassia and J.S.\ Vitter, ``Parallel Transitive Closure and
Point Location in Planar Structures,`` SIAM J.\ Computing,
vol.\ 20, no.\ 4, pp.\ 708-725, 1991.
% R.\ Tamassia and J.S.\ Vitter, ``Optimal Parallel Algorithms for
% Transitive Closure and Point Location in Planar Structures,''
% Proc.\ ACM Symp.\ on Parallel Algorithms and Architectures,
% pp.\ 399-408, 1989.
\label{pa-WQ} \end{paper}
 
\begin{paper}
M.\ F\"urer, X.\ He, M.-Y.\ Kao, and B.\ Raghavachari, ``$O(n \log\log
n)$-Work Parallel Algorithms for  Straight-Line Grid Embeddings of
Planar Graphs,`` Proc.\ ACM Symp.\ on Parallel Algorithms and
Architectures, 1992.
\label{pa-FRHK92} \end{paper}

\begin{paper}
M.\ F\"urer, X.\ He, M.-Y.\ Kao, and B.\ Raghavachari, ``Optimal Parallel Algorithms for Straight-Line Grid Embeddings of
Planar Graphs,`` SIAM J.\ Discrete Mathematics, (to appear).
\label{pa-FRHK93} \end{paper}

\begin{paper}
F.\ Dehne, H.\ Djidjev and J.-R.\ Sack, ``An Optimal PRAM Algorithm for
Planar Convex Embedding,'' Manuscript, 1993.
\label{pa-Sack} \end{paper}
 
\subsection{Dynamic Algorithms}
 
A reference model for dynamic drawing algorithms is given in:
 
\begin{paper}
R.F.\ Cohen, G.\ Di~Battista, R.\ Tamassia, I.G.\ Tollis, and P.\
Bertolazzi, ``A Framework for Dynamic Graph Drawing,'' Proc.\ ACM
Symp.\ on Computational Geometry, pp.\ 261-270, 1992.
\label{pa-P12} \end{paper}
The paper contains also several results on dynamic problems within the
proposed model.
 
An on-line planarity testing algorithm supporting insertions of
vertices and edges with logarithmic query/update time is presented in:
 
\begin{paper}
G.\ Di~Battista and R.\ Tamassia, ``Incremental Planarity Testing,''
Proc.\ 30th IEEE Symp.\ on Foundations of Computer Science,
pp.\ 436-441, 1989.
 \label{pa-RS} \end{paper}

The best result on fully dynamic planarity testing (where both insertions
and deletions are allowed) is an algorithm with $O(\sqrt{n})$ amortized
query and update time, given in

\begin{paper}
D.\ Eppstein, Z.\ Galil, G.F.\ Italiano, and T.H.\ Spencer, ``Separator
Based Sparsification for Dynamic Planar Graph Algorithms,'' Proc.\ ACM
Symp.\ on Theory of Computing, pp.\ 208-217, 1993.
\label{pa-Italiano} \end{paper}
 
An algorithm for drawing trees in a dynamic environment is presented
in:
 
\begin{paper}
S.\ Moen, ``Drawing Dynamic Trees,'' IEEE Software, vol.\ 7, pp.\ 21-28,
1990.
\label{pa-SG} \end{paper}

The incremental construction of an orthogonal drawing is investigated in

\begin{paper}
K.\ Miriyala, S.W.\ Hornick, and R.\ Tamassia, ``An Incremental
Approach to Aesthetic Graph Layout,'' Proc.\ Int.\ Workshop on
Computer-Aided Software Engineering (CASE '93), pp.\ 297 (1993).
\label{pa-andersen} \end{paper}

An important consideration in dynamic graph layout
is {\em preserving the mental map}: when a change is made
to a graph by the user, the re-application of a layout
algorithm may destroy the user's ``mental map''.
Models and techniques for preserving the mental map are discussed in
 
\begin{paper}
P. Eades, W. Lai, K. Misue and K. Sugiyama, ``Preserving the Mental Map
of a Diagram,'' Proc.\ Compugraphics 91, Portugal 1991, pp.\ 24-33.
\label{pa-PDEu}
\end{paper}
 
\begin{paper}
K. Lyons, ``Cluster Busting in Anchored Graph Drawing,'' Proc.\ CAS
Conference, IBM Centre for Advanced Studies, Toronto 1992, pp.\ 327-338.
\label{pa-PDEv}
\end{paper}

\begin{paper}
K. Bohringer and F. Newbery Paulisch, ``Using Constraints to Achieve
Stability in Automatic Graph Layout Algorithms,'' Proc.\ ACM CHI 90,
(1990) pp 43-51.
\label{pa-PDEw}
\end{paper}


\subsection{Three Dimensions}
 
Three-dimensional drawings of graphs are investigated in
[\ref{pa-SF}, \ref{pa-PDEs}] and

\begin{paper}
G.G.\ Robertson, J.D.\ Mackinlay, and S.K.\ Card, ``Cone Trees:
Animated 3D Visualizations of Hierarchical Information,'' Proc.\ CHI,
pp.\ 189-193, 1991.
\label{pa-cone}
\end{paper}

\begin{paper}
S.P. Reiss, ``A Framework for Abstract 3D Visualization,''
Proc.\ IEEE Symp.\ on Visual Languages (VL '93), 1993.
\label{pa-Reiss}
\end{paper}

\begin{paper}
A.\ Rudich, D.\ Zernik and G.\ Zodik.
``Visage --- Visualization of Attribute Graphs: A foundation
for a Parallel Programming Environment,''
Environments and Tools for Parallel Scientific Computing
North Holland, Ed. J.J. Dongarra and B. Tourancheau, pp.\ 171-192.
\label{pa-Dror}
\end{paper}

\subsection{Hypergraphs}
 
Two notions of planarity for hypergraphs and NP-completeness results
are given in:
 
\begin{paper}
D.S.\ Johnson and H.O.\ Pollak, ``Hypergraph Planarity and the
Complexity of Drawing Venn Diagrams,'' J.\ Graph Theory, vol.
10, no.\ 3, pp.\ 309-325, 1987.
\label{pa-RO} \end{paper}
 
A new formalism for representing graphs and hypergraphs, called {\em
higraph}, is introduced in:
 
\begin{paper}
D.\ Harel, ``On Visual Formalisms,'' Communications of the ACM, vol.
31, no.\ 5, pp.\ 514-530, 1988.
\label{pa-SO} \end{paper}
 
An algorithm for drawing hypergraphs is presented in:
 
\begin{paper}
E.\ M\"akinen, ``How to Draw a Hypergraph,'' International Journal of
Computer Mathematics 34 (1990), 177-185.
\label{pa-RW} \end{paper}


\subsection{Separator-Based Algorithms}

Separator-based algorithms for area-efficient (nonplanar) orthogonal
drawings of trees, planar graphs, and other computationally interesting
networks (e.g., $d$-dimensional mesh, cube-connected cycles, and
shuffle-exchange) are studied in~[\ref{pa-YA}] and:

\begin{paper}
C.E.\ Leiserson, ``Area-Efficient Graph Layouts (for VLSI),''
Proc.\ IEEE Symp.\ on Foundations of Computer Science, pp.\ 270-281, 1980.
\label{pa-Leiserson} \end{paper}

\begin{paper}
D.\ Sherlekar, ``Minimizing the Maximum Wire Length in VLSI
Graph Layouts,`` Proc.\ 28th Annual Allerton Conf., 1990.
\label{pa-Sherlekar} \end{paper}


Goodrich gives an optimal algorithm for the separator decomposition of
planar graphs, which improves the time complexity of separator-based
algorithm for planar graphs.

\begin{paper}
M.T.\ Goodrich, ``Planar Separators and Parallel Polygon
Triangulation,'' Proc.\ 24th ACM Symp.\ on Theory of Computing, pp.
507-516, 1992.
\label{pa-Goodrich} \end{paper}

 
\subsection{Declarative Methods}
 
Several recent techniques for graph drawing emphasize the expression of
the aesthetics rather than the algorithmic complexity of achieving the
aesthetics. These techniques, called {\em declarative techniques},
often require very large computational resources, and are perhaps outside
the scope of this bibliography.  An example is the use of genetic
algorithms:
 
\begin{paper}
C.\ Kosak and J.\ Marks, ``A Parallel Genetic Algorithm for
Network-Diagram Layout,'' Proc.\ 4th Int.\ Conf.\ on Genetic Algorithms
(ICGA91), 1991.
\label{pa-P28} \end{paper}
 
\begin{paper}
C.\ Kosak, J.\ Marks, and S.\ Shieber, ``New Approaches to Automating
Network-Diagram Layout,'' IEEE Trans. on Systems, Man, and
Cybernetics.  To appear. 1993.
\label{pa-PDEy}
\end{paper}
 
Other examples include the simulated annealing methods of [\ref{pa-PDEq}],
and the constraint resolution methods of [\ref{pa-P47}].

The formal specification of constraints in the drawing of a graph is
studied in [\ref{pa-P8}] and in

\begin{paper}
J.D.\ Mackinlay, ``Automating the Design of Graphical Presentations of
Relational Information,'' ACM Transactions on Graphics, vol. 5, no. 2,
1986.
\label{pa-PDEx}
\end{paper}
 
\begin{paper}
J.\ Marks, ``A Formal Specification Scheme for Network Diagrams that
Facilitates Automated Design,'' J.\ Visual Languages and Computing,
vol.\ 2, pp.\ 395-414, 1991.
\label{pa-Marks}
\end{paper}

\begin{paper}
E.\ Dengler, M.\ Friedell, and J.\ Marks, ``Constraint-Driven Diagram
Layout,'' Proc.\ IEEE Symp.\ on Visual Languages (VL '93), 1993.
\label{pa-Dengler}
\end{paper}

\begin{paper}
S.\ Deal, ``The Specification and Recognition of Optimal Layout
Configurations for Graph Structures,'' Ph.D.\ dissertation,
Dept.\ Computer Science, Univ.\ College London, 1989.
\label{pa-Deal}
\end{paper}

An approach to drawing graphs based on graph grammars is presented by
Brandenburg:

\begin{paper}
F.J. Brandenburg, ``Layout Graph Grammars: the Placement Approach,''
Graph-Grammars and Their Application to Computer Science, Proc. 4th
Int.  Workshop, Bremen, Germany, 1990, Lecture Notes in Computer
Science 532, pp.\ 144-156. Springer-Verlag, 1991.
\label{pa-Brandenburg}
\end{paper}

A visual approach to graph drawing is presented in:

\begin{paper}
I.F. Cruz, R. Tamassia and P. Van Hentenryck, ``A Visual Approach to
Graph Drawing,'' Manuscript, Brown University, 1993.
\label{pa-Cruz}
\end{paper}


\subsection{Aesthetics}
 
A discussion of graph drawing aesthetics appears in:
 
\begin{paper}
C.\ Esposito, ``Graph Graphics: Theory and Practice,'' Comput.\ Math.
Applic., vol.\ 15, no.\ 4, pp.\ 247-253, 1988.
\label{pa-SL}
 
\end{paper}
An experimental study of aesthetics used in Entity Relationship
diagrams is reported in:
 
\begin{paper}
C.\ Batini, L.\ Furlani, and E.\ Nardelli, ``What is a Good Diagram?  A
Pragmatic Approach,'' Proc.\ 4th Int.\ Conf.\ on the Entity
Relationship Approach, Chicago, 1985.
\label{pa-ST} \end{paper}
 
An analogous study in the field of data structure diagrams is in:
 
\begin{paper}
C.\ Ding and P.\ Mateti, ``A Framework for the Automated Drawing of
Data Structure Diagrams,'' IEEE Trans.\ on Software Engineering,
vol.\ SE-16, no.\ 5, pp.\ 543-557, 1990.
\label{pa-P7} \end{paper}


\subsection{Compound Graphs}
 
In {\em compound digraphs}, edges represent both adjacency and
inclusion relations. Compound graphs and similar structures (such as
{\em higraphs} [\ref{pa-SO}]) are powerful modeling tools for
relational information.
 
Layout algorithms for compound digraphs are given in [\ref{pa-P47}] and
 
\begin{paper}
K. Sugiyama and K. Misue, ``Visualization of Structural Information:
Automatic Drawing of Compound Digraphs,'' IEEE Transactions on Systems,
Man and Cybernetics, vol. 21, no. 4, pp. 876-892, 1991.
\label{pa-RP} \end{paper}


\subsection{Angles}
 
An interesting aesthetic is to ensure that the angles between the
segments that represent edges are not too small.  Studies of this
aesthetic applied to planar straight-line drawings are in:
 
\begin{paper}
G.\ Vijayan, ``Geometry of Planar Graphs with Angles,'' Proc.
ACM Symp.\ on Computational Geometry, pp.\ 116-124, 1986.
\label{pa-P20} \end{paper}
 
\begin{paper}
S.\ Malitz and A.\ Papakostas, ``On the Angular Resolution of Planar
Graphs,'' Proc. 24th ACM Symp.\ on the Theory of Computing,
pp.\ 527-538, 1992.
\label{pa-P21} \end{paper}

\begin{paper}
G.\ Di Battista and L.\ Vismara, ``Angles of Planar Triangular
Graphs,'' Proc.\ ACM Symp.\ on Theory of Computing, pp.\ 431-437, 1993.
\label{pa-DV93} \end{paper}

It is shown in~[\ref{pa-P21}] that it is always possible to construct a
straight line planar drawing whose smallest angle is $\Omega(\alpha^d)$,
where $0 < \alpha < 1$, and $d$ is the maximum degree of a vertex of
the graph. Further results are given for outerplanar graphs.

A similar problem, but for nonplanar graphs, is considered in:
 
\begin{paper}
M.\ Formann, T.\ Hagerup, J.\ Haralambides, M.\ Kaufmann,
F.T.\ Leighton, A.\ Simvonis, E.\ Welzl, and G.\ Woeginger, ``Drawing
Graphs in the Plane with High Resolution,'' Proc.\ IEEE Symp.\ on
Foundations of Computer Science, pp.\ 86-95, 1990.
(To appear in SIAM J. on Computing, 1993.)
\label{pa-P22} \end{paper}

It is shown that it is always possible to construct a drawing whose
smallest angle between the edges incident at a vertex is
$\Omega(1/d^2)$, where $d$ is the maximum degree of a vertex of the
graph.  Other results are given for particular classes of graphs.


% -------------------------------------------------------------------
 
\section{Open Problems} \label{se-open}
 
Despite the abundance of literature on graph drawing, many theoretical
and practical problems are still open. A few of the most promising
directions for further research are listed below.

\begin{description}
 
\item[Performance Bounds for Planarization] Although crossing
minimization is a fundamental issue, nontrivial performance bounds
have not been found for any heuristic. A guaranteed heuristic would be
very important both for aesthetic graph drawing and VLSI layout.
% Further, an algorithm with a performance guarantee for finding a
% maximum planar subgraph would be very welcome.
%	Dyer Fouls and Frieze,
%	AN EFFICIENT HEURISTIC FOR IDENTIFYING
%	A MAXIMUM WEIGHT PLANAR SUBGRAPH
%	European J of Ops Research 20, 102-114.
 
% \item[Upward Planarity Testing] There is a combinatorial
% characterization of the acyclic digraphs that admit a planar upward
% drawing [\ref{pa-RE}, \ref{pa-RF}]. However, no polynomial time
% algorithm for testing ``upward planarity'' in general acyclic digraphs
% is known.
 
\item[Simple Planarity Testing] The known planarity algorithms
that achieve linear time complexity (Section~\ref{se-planartest}) are
all difficult to understand and implement. This is a serious limitation
for their use in practical systems. A simple and efficient algorithm
for testing the planarity of a graph and constructing planar
representations would be a significant contribution.
 
\item[General Strategy for Straight-Line Drawings] General
strategies have been successfully developed for hierarchical drawings
(Section~\ref{se-dags}) and orthogonal grid drawings
(Section~\ref{se-polyline}). These techniques take several aesthetics
into account. The simplicity of straight-line drawings is very
appealing, and a general straight-line drawing technique would find
immediate applications.  The most versatile technique for planar
straight-line drawings is the the one by Kant~[\ref{pa-P34}].
Some further progress in this direction is reported in~[\ref{pa-P10}].
 
\item[Dynamic Drawing Algorithms] Several graph manipulation
systems allow the user to interactively modify a graph by inserting and
deleting vertices and edges. Data structures that allow for fast
restructuring of the drawing would be very useful. Especially important
is the {\em dynamic planarity testing} problem, where we want a data
structure for planar graphs that supports in polylogarithmic time the
following operations: (a) testing whether a new edge can be added while
preserving planarity; (b) adding vertices and edges which preserve
planarity; and (c) removing vertices and edges.  When only insertions
are allowed, this problem can be efficiently solved in $O(\log n)$ time
per test or update, as shown in [\ref{pa-RS}].  However, the best
solution for the general problem (insertions and deletions) has
$O(\sqrt{n})$ amortized query and update time~[\ref{pa-Italiano}].

\item[Complexity of Bend Minimization] Several issues on the
computational complexity of minimizing bends in planar orthogonal
drawings are open.  If the embedding is fixed, bend minimization can be
done in time $O(n^2 \log n)$~[\ref{pa-XZ}]. Particular classes of
graphs are investigated in [\ref{pa-PXX1}]. It would be interesting to
improve on the sequential complexity and to develop a fast parallel
algorithm for the fixed-embedding problem.

\item[Area of Planar Upward Drawings of Trees] The
area requirement of upward planar drawings of trees has been studied
in~[\ref{pa-P2}, \ref{pa-GGT93}], where tight bounds are given for
polyline drawings ($\Theta(n)$) and orthogonal drawings ($\Theta(n
\log\log n)$).  The area requirement of straight-line drawings is not
known instead.  The best upper bound is $O(n \log n)$, while only the
trivial $\Omega(n)$ lower bound is known.

\item[Angular Resolution of Planar Straight-Line Drawings] The
angular resolution of a planar straight-line drawing is the minimum
angle formed by two edges incident on the same vertex.  It has been
shown that a planar graph of degree $d$ has a drawing with angular
resolution $\Omega(1/7^d)$~[\ref{pa-P21}].   Only the trivial $O(1/d)$
upper bound is known.

\item[Size Bounds for Three Dimensional Grid Drawings]
Graph drawing systems which exploit for three dimensions already exist
but very little theory has been developed. In particular, practically
nothing is known about upper and lower bounds for the sides of the
enclosing rectangular prism of a three dimensional grid drawing.

\end{description}

\section*{Acknowledgements}
 
The authors wish to thank the many graph drawers who have pointed out
errors and omissions in the first three versions, and those who have
helped with updates to create this fourth version.

% -------------------------------------------------------------------

\appendix

\ifesp \else \clearpage \fi

\section{Graph Drawing '93} \label{app-gd}

The following papers have been presented at {\em Graph
Drawing'93}~[\ref{pa-GD93}]. \bigskip

\begin{small}

\newcommand{\gdpaper}[2]{\item[~] {#1}. {\em #2}}

\newcommand{\Aab}{A.\ Bergey}
\newcommand{\Tab}{Automorphisms and Genus on Generalised Maps}

\newcommand{\Aac}{P.\ Bose, W.\ Lenhart and G.\ Liotta}
\newcommand{\Tac}{Characterizing Proximity Trees}

\newcommand{\Aad}{P.\ Bose, H.\ Everett, S.\ Fekete, A.\ Lubiw, H.\ Meijer,
			K.\ Romanik, T.\ Shermer and S.\ Whitesides}
\newcommand{\Tad}{On a Visibility Representation for Graphs in Three Dimensions}

\newcommand{\Aae}{F.\ J.\ Brandenburg and P.\ Eades}
\newcommand{\Tae}{A Note on free Drawings of Binary Trees on a Square}

\newcommand{\Aaf}{M.\ Bousset}
\newcommand{\Taf}{A Flow Model of Low Complexity for Twisting a Layout}

\newcommand{\Aag}{J.\ Chen, S.\ P.\ Kanchi and J.\ L.\  Gross}
\newcommand{\Tag}{On Graph Drawings with Smallest Number of Faces}

\newcommand{\Aah}{M.\ K.\ Coleman and D.\ S.\ Parker}
\newcommand{\Tah}{Aesthetics-based Graph Layout for Human Consumption}

\newcommand{\Aai}{F.\ Dehne, H.\ Djidjev and J.-R.\ Sack}
\newcommand{\Tai}{An Optimal PRAM Algorithms for Planar Convex Embedding}

\newcommand{\Aaj}{A.\ Denise}
\newcommand{\Taj}{Generation of Random Planar Maps}

\newcommand{\Aba}{G.\ Di Battista, G.\ Liotta and F.\ Vargiu}
\newcommand{\Tba}{Convex and non-Convex Cost Functions of Orthogonal Representations}

\newcommand{\Abb}{G.\ Di Battista and L.\ Vismara}
\newcommand{\Tbb}{Topology and Geometry of Planar Triangular Graphs}

\newcommand{\Abc}{P.\ Eades and T.\ Lin}
\newcommand{\Tbc}{Algorithmic and Declarative Approaches to Aesthetic Layout}

\newcommand{\Abd}{P.\ Eades and X.\ Mendon\c ca}
\newcommand{\Tbd}{Heuristics for Planarization by Vertex Splitting}

\newcommand{\Abe}{H.\ ElGindy, M.\ Houle, B.\ Lenhart, M.\ Miller,
			D.\ Rappaport and S.\ Whitesides}
\newcommand{\Tbe}{Dominance Drawings of Bipartite Graphs}

\newcommand{\Abf}{U.\ Finke and K.\ Hinrichs}
\newcommand{\Tbf}{Computing the Overlay of Regular Planar Subdivisions
			in Linear Time}

\newcommand{\Abg}{U.\ F\"o\ss meier and M.\ Kaufmann}
\newcommand{\Tbg}{An Approach for Bend-Minimal Upward Drawing}

\newcommand{\Abh}{S.\ P.\ Foubister and C.\ Runciman}
\newcommand{\Tbh}{The Display, Browsing and Filtering of Graph-Trees}

\newcommand{\Abi}{A.\ Garg and R.\ Tamassia}
\newcommand{\Tbi}{Efficient Computation of Planar Straight-Line Upward Drawings}

\newcommand{\Abj}{M.\ Himsolt}
\newcommand{\Tbj}{A View to Graph Drawing Algorithms through Graph$^{\rm Ed}$}

\newcommand{\Aca}{S.\ B.\ Johansen}
\newcommand{\Tca}{Implementation of the Planarity Testing Algorithm by
Demoucron, Malgrange and Pertuiset}

\newcommand{\Acb}{M.\ J\"unger and P.\ Mutzel}
\newcommand{\Tcb}{Maximum Planar Subgraphs and Nice Embeddings: Practical
			Layout Tools}

\newcommand{\Acc}{G.\ Kant}
\newcommand{\Tcc}{A More Compact Visibility Representation}

\newcommand{\Acd}{G.\ Kant and X.\ He}
\newcommand{\Tcd}{Two Algorithms for Finding Rectangular Duals of Planar Graphs}

\newcommand{\Ace}{G.\ Kant, G.\ Liotta, R.\ Tamassia and I.\ G.\ Tollis}
\newcommand{\Tce}{Area Requirement of Visibility Representations of Trees}

\newcommand{\Acf}{J.\ Kratochv\'\i l and Ji\v{r}\'{\i} Matou\v{s}ek}
\newcommand{\Tcf}{Complexity of Intersection Classes of Graphs}

\newcommand{\Acg}{A.\ Lubiw}
\newcommand{\Tcg}{Cone Visibility Graphs}

\newcommand{\Ach}{J.\ Manning}
\newcommand{\Tch}{Symmetric Drawings of Graphs}

\newcommand{\Aci}{C.\ L.\ McCreary, C.\ L.\ Combs, D.\ H.\ Gill and
			J.\ V. Warren}
\newcommand{\Tci}{An Automated Graph Drawing System Using Graph Decomposition}

\newcommand{\Acj}{M.\ S.\ Miyauchi}
\newcommand{\Tcj}{Algorithms for Embedding Graphs Into a 3-page Book}

\newcommand{\Ada}{B.\ Mohar}
\newcommand{\Tda}{Generalizing Kuratowski's Theorem}

\newcommand{\Adb}{S.\ C.\ North}
\newcommand{\Tdb}{Drawing Ranked Digraphs with Recursive Clusters}

\newcommand{\Adc}{T.\ Ozawa}
\newcommand{\Tdc}{Planar Graph Embedding with a Specified Set of
			Face-Independent Vertices}

\newcommand{\Add}{J.\ Pach}
\newcommand{\Tdd}{New Developments in Geometric Graph Theory}

\newcommand{\Ade}{S.\ Pimont and M.\ Terrenoire}
\newcommand{\Tde}{Characterization and Construction of the Rectangular Dual
			of a Graph}

\newcommand{\Adf}{T.\ Pisanski}
\newcommand{\Tdf}{Recognizing Symmetric Graphs}

\newcommand{\Adg}{T.\ M.\ Przytycka and J.\ H.\ Przytycki}
\newcommand{\Tdg}{A Simple Construction of High Representativity Triangulations}

\newcommand{\Adh}{B.\ Regan}
\newcommand{\Tdh}{Two Algorithms for Drawing Trees in Three Dimensions}

\newcommand{\Adi}{I.\ Rival}
\newcommand{\Tdi}{Upward Drawing on Surfaces}

\newcommand{\Adj}{J.\ F.\ Small}
\newcommand{\Tdj}{A Unified Approach to Testing, Embedding and Drawing Planar Graphs}

\newcommand{\Aea}{H.\ Stamm-Wilbrandt}
\newcommand{\Tea}{A Simple Linear-Time Algorithm for Embedding Maximal Planar Graphs}

\newcommand{\Aeb}{I.\ G.\ Tollis and C.\ Xia}
\newcommand{\Teb}{Graph Drawing Algorithms for the Design and Analysis of Telecommunication Networks}

\newcommand{\Aec}{D.\ Tunkelang}
\newcommand{\Tec}{A Layout Algorithm for Undirected Graphs}

\newcommand{\Aed}{G.\ Zin\ss meister}
\newcommand{\Ted}{Layout of Trees with Attribute Graph Grammars}

\newcommand{\Aee}{I.\ F.\ Cruz, R.\ Tamassia and P.\ Van Hentenryck}
\newcommand{\Tee}{A Visual Approach to Graph Drawing}

\newcommand{\Aef}{P.\ O.\ de Mendez}
\newcommand{\Tef}{On Lattice Structures Induced by Orientations}

\newcommand{\Aeg}{H.\ de Fraysseix and P.\ Rosenstiehl}
\newcommand{\Teg}{The Left-Right Algorithm for Planarity Testing and Embedding}

\newcommand{\Aeh}{B.\ Mohar and P.\ Rosenstiehl}
\newcommand{\Teh}{Tessellation and Visibility Representations of Maps on the Torus}
% \newcommand{\Teh}{Visibility on a Torus}

\newcommand{\Aei}{H.\ de Fraysseix, P.\ O.\ de Mendez and P.\ Rosenstiehl}
\newcommand{\Tei}{On Triangle Contact Graphs}
% \newcommand{\Tei}{Maximal Planar Graphs are Triangle-Contact Graphs}

\newcommand{\Tej}{Representations of Planar Graphs}
\newcommand{\Aej}{C.\ Thomassen}

\newcommand{\Tfa}{Circle Packing Representations in Polynomial Time}
\newcommand{\Afa}{B.\ Mohar}

\newcommand{\Tfb}{On the Four Colour Problem}
\newcommand{\Afb}{C.\ Berge}

% -------------------------------------------

\begin{list}{}{%
\setlength{\leftmargin}{2pt} \setlength{\parsep}{0pt}
\setlength{\labelwidth}{0in}
}

\begin{description}  \parsep 0pt \itemsep 0pt

\item[\sc Session~0: Invited Lecture. \rm Chair: Pierre Rosenstiehl ]

\gdpaper{\Tfb}{\Afb}

\item[\sc Session~1: Geometric Graph Theory.  \rm Chair: Roberto Tamassia ]

\gdpaper{\Tdd}{\Add}

\item[\sc Session~2: Trees.  \rm Chair: Giuseppe Di Battista ]

\gdpaper{\Tac}{\Aac}
\gdpaper{\Tae}{\Aae}
\gdpaper{\Tdh}{\Adh}
\gdpaper{\Tce}{\Ace}

\item[\sc Session~3: Upward Drawings.  \rm Chair: Takao Nishizeki ]

\gdpaper{\Tbi}{\Abi}
\gdpaper{\Tbg}{\Abg}

\item[\sc Session~4: Invited Lecture.  \rm  Chair: Hubert de Fraysseix ]

\gdpaper{\Tej}{\Aej}

\item[\sc Session~5: Representations in the Plane I.  \rm  Chair: Anna Lubiw]

\gdpaper{\Tef}{\Aef}
\gdpaper{\Tcf}{\Acf}
\gdpaper{\Tei}{\Aei}

\item[\sc Session~6: Representations in the Plane II.  \rm  Chair: Ioannis G.\ Tollis]

\gdpaper{\Tde}{\Ade}
\gdpaper{\Tcd}{\Acd}
\gdpaper{\Tcc}{\Acc}
\gdpaper{\Tcg}{\Acg}

\item[\sc Session~7: Beyond the Plane I.  \rm  Chair: J\'anos Pach ]

\gdpaper{\Tfa}{\Afa}
\gdpaper{\Tda}{\Ada}
\gdpaper{\Tab}{\Aab}
\gdpaper{\Tdi}{\Adi}

\item[\sc Session~8: Beyond the Plane II.  \rm  Chair: Ivan Rival ]

\gdpaper{\Teh}{\Aeh}
\gdpaper{\Tdg}{\Adg}
\gdpaper{\Tad}{\Aad}
\gdpaper{\Tag}{\Aag}

\item[\sc Session~9: Drawings and Flows.  \rm  Chair: Michael Kaufmann ]

\gdpaper{\Taf}{\Aaf}
\gdpaper{\Tba}{\Aba}
\gdpaper{\Tbb}{\Abb}

\item[\sc Session~10: Complexity.  \rm  Chair: Joseph Manning ]

\gdpaper{\Tai}{\Aai}
\gdpaper{\Tcj}{\Acj}
\gdpaper{\Tbe}{\Abe}
\gdpaper{\Tbf}{\Abf}
\gdpaper{\Taj}{\Aaj}

\item[\sc Session~11: Symmetry.  \rm  Chair: Peter Eades ]

\gdpaper{\Tch}{\Ach}
\gdpaper{\Tdf}{\Adf}

\item[\sc Session~12: Declarative Approaches.  \rm  Chair: Franz J.\ Brandenburg]

\gdpaper{\Tbc}{\Abc}
\gdpaper{\Tee}{\Aee}
\gdpaper{\Ted}{\Aed}
\gdpaper{\Tbh}{\Abh}

\item[\sc Session~13: Graph Drawing Systems I.  \rm  Chair: David Rappaport]

\gdpaper{\Tec}{\Aec}
\gdpaper{\Tdb}{\Adb}

\item[\sc Session~14: Graph Drawing Systems II.  \rm  Chair: Robert F.\ Cohen]

\gdpaper{\Teb}{\Aeb}
\gdpaper{\Tbj}{\Abj}
\gdpaper{\Tci}{\Aci}

\item[\sc Session~15: Embedding and Planarization I.  \rm  Chair: Bojan Mohar]

\gdpaper{\Tcb}{\Acb}
\gdpaper{\Tbd}{\Abd}
\gdpaper{\Tdc}{\Adc}

\item[\sc Session~16: Embedding and Planarization II.  \rm  Chair: Herbert Fleischner]

\gdpaper{\Tca}{\Aca}
\gdpaper{\Tdj}{\Adj}
\gdpaper{\Tea}{\Aea}

\end{description}

\end{list}

\end{small}
 
% -------------------------------------------------------------------

\ifesp \else \clearpage \fi

\section{Graph Drawing '94}  \label{app-gdd}

\begin{center}
\LARGE\sf		Call for Papers, Demos, and Participation
\\[1.0ex]\LARGE\bf	Graph Drawing '94
\\[1.5ex]\Large		DIMACS Workshop on Graph Drawing
\\[0.5ex]\large		Princeton, New Jersey, October 10-12, 1994
\end{center}

\thispagestyle{empty}

\paragraph{Scope}

Graph drawing addresses the problem of constructing geometric
representations of abstract graphs and networks.  The automatic
generation of drawings of graphs has important applications in key
computer technologies such as software engineering, database design,
and visual interfaces.  Recent progress in algorithm design,
computational geometry, topological graph theory, and order theory has
considerably affected the evolution of this field, and has widened the
range of issues being investigated.

\paragraph{Call for Participation}

The aim of {\em Graph Drawing '94\/} ({\em GD~'94}) is to cover the
major trends in the area.  The format of the workshop will be
informal.  Industry representatives are welcome to attend.  It is
anticipated that the workshop will further collaborative efforts
between computer scientists, mathematicians, and applied researchers.
{\em GD~'94} follows the {\em GD '93\/} ALCOM Workshop, held in Paris,
and the {\em GD '92\/} Work Meeting, held in Rome.  {\em GD~'94} is
sponsored by {\em DIMACS}, the NSF Science and Technology Center in
Discrete Mathematics and Theoretical Computer Science hosted by Rutgers
University, Princeton University, AT\&T Bell Laboratories, and
Bellcore.  Limited financial support for partial coverage of expenses
of selected participants is available.  Priority will be given to
junior researchers and Ph.D.\ students.  To receive full consideration,
requests should be made to one of the organizers by {\bf July~20}.

\paragraph{Call for Papers}
%
Papers describing original research and surveys addressing open
problems are sought.  Areas of interest include, but are not limited
to:
%
\begin{itemize}  \itemsep 0pt \parsep 0pt \topsep 0pt
%
\item	Applications of graph drawing, such as software
	visualization,user interfaces, database queries, information
	browsers, and computer-aided instruction.
%
\item	Tools and systems for graph drawing.
%
\item   Topological graph theory; combinatorial issues such as
	planarity, orientations, and orders.
%
\item	Geometric graph theory; 2- and 3-dimensional representations of
	graphs and hypergraphs by geometric relations, such as
	visibility, proximity, intersection, and inclusion.
%
\item	Models, algorithms, and techniques for drawing graphs,
	such as partitioning, layering, orientation, planarization,
	dynamic layout restructuring, graph grammars, and declarative
	specifications.
%
\item	Drawing algorithms for specific families of graphs, such
	as trees, planar graphs, and order digraphs.
%
\end{itemize}

\paragraph{Call for Demos}
%
A great deal of research in graph drawing is motivated by applications
to systems for viewing and interacting with graphs.  Also, recent
theoretical advances in graph drawing need to be implemented in
practical systems.  Submissions for demos to be presented at {\em
GD~'94} are solicited.  Areas of interest include, but are not limited
to:
%
\begin{itemize}  \itemsep 0pt \parsep 0pt \topsep 0pt
%
\item	Mathematical visualization of graphs.
%
\item	Novel graph-based software visualization and software
	engineering applications.
%
\item	Database visualization with graphs and hypergraphs.
%
\item	Programming environments for graphs and their layouts.
%
\item	Algorithm animation with graphs.
%
\item	User interfaces for viewing graphs, e.g., interactive
	exploration of large graphs and presentation of dynamic graphs.
%
\end{itemize}

\paragraph{Submission of Papers and Demos}

The program committee invites three types of submissions:
{\em regular papers} (submit a 6-12 page extended abstract);
{\em short papers} (submit a 1-4 page abstract); and
{\em demos} (submit a 1-4 page abstract, descriptive screen
dumps, and a list of the hardware needed).

The deadline for submissions is {\bf July~20}.  Submissions can be made
by email or hardcopy.  {\em Email submissions} in \LaTeX, postscript
(compressed and uuencoded), or plain text should be sent to Roberto
Tamassia ({\tt rt@cs.brown.edu}).  {\em Hardcopy submissions} should be
sent in 10 copies to:
%
Ioannis G. Tollis, Dept.\ of Computer Science, The University of
Texas at Dallas, P.O.\ Box 830688, EC 31, Richardson, TX 75083-0688
(USA).

Notification of acceptance or rejection will be done by email on or
before {\bf September~1}.  Camera-ready versions are due at the
workshop.  The proceedings of {\em GD~'94} will include short papers,
regular papers, and demo descriptions, and will be published after the
workshop by Springer-Verlag or the American Mathematical Society
(AMS).

\paragraph{Program Committee}
%
{\em Franz J. Brandenburg}		(Univ. Passau, Germany),
{\em Giuseppe Di Battista}		(Univ.\ Rome, Italy),
{\em Hubert de Fraysseix}		(CNRS, France),
{\em Alberto O. Mendelzon}		(Univ.\ Toronto, Canada),
{\em Takao Nishizeki}			(Tohoku Univ., Japan),
{\em Stephen North}			(AT\&T Bell Labs, USA),
{\em Ivan Rival}			(Univ.\ Ottawa, Canada),
{\em Roberto Tamassia}, co-chair	(Brown Univ., USA),
{\em Ioannis G. Tollis}, co-chair	(Univ. Texas at Dallas, USA),
{\em Sue Whitesides}			(McGill Univ., Canada).
%

\paragraph{Organizers} ~

{\em Roberto Tamassia}	({\tt rt@cs.brown.edu})

{\em Ioannis G. Tollis}	({\tt tollis@utdallas.edu})

\paragraph{Coordinator} ~

{\em Pat Toci}		({\tt toci@dimacs.rutgers.edu})


% -------------------------------------------------------------------

\ifesp \else \clearpage \fi

\twocolumn[\section{Index of Authors} \label{app-index}]

\begin{description} \small \setlength{\itemsep}{0in}

\item Abe, S.  \ref{pa-XK}.

\item Ainslie, P.J.  \ref{pa-SI}.

\item Andreae, T. \ref{pa-Andreae92}

\item Aoudja, F.  \ref{pa-RK}.

\item Arya, A.  \ref{pa-QD}.

\item Aschim, F.  \ref{pa-QL}.

\item Atallah, M.J.  \ref{pa-XG}, \ref{pa-XX}, \ref{pa-RX}.

\item Batini, C.  \ref{pa-QB}, \ref{pa-R6}, \ref{pa-QF}, \ref{pa-QH},
\ref{pa-QP}, \ref{pa-QR}, \ref{pa-ST}.

\item Baudon, O.  \ref{pa-Baudon}.

\item Bayley, D.A.  \ref{pa-R7}.

\item Beccaria, M.  \ref{pa-P11}.

\item Becker, B.  \ref{pa-XT}, \ref{pa-XU}.

\item Berger, B.  \ref{pa-PDEm}.

\item Bernard, M.A.  \ref{pa-QX}.

\item Bertolazzi, P.  \ref{pa-P16}, \ref{pa-P42}, \ref{pa-esa},
\ref{pa-P18}, \ref{pa-BCDTT94}, \ref{pa-P11}, \ref{pa-P12}.

\item Bhasker,  J.  \ref{pa-QW}.

\item Bhatt, S.  \ref{pa-WC}.

\item Birgisson, B.  \ref{pa-UD}.

\item Bodlaender, H.L. \ref{pa-P3}.

\item Bohringer, K. \ref{pa-PDEw}.

\item Bondy, J.  \ref{pa-RA}.

\item Booth, K. \ref{pa-RD}.

\item Bordier, J.  \ref{pa-Bordier}.

\item Bousset, M. \ref{pa-P41}.

\item Brandenburg, F.J.  \ref{pa-RM}, \ref{pa-Brandenburg}.

\item Brodie, M.  \ref{pa-RJ}.

\item Brown, G.  \ref{pa-RJ}, \ref{pa-R5}, \ref{pa-QE}.

\item Brown, M..  \ref{pa-SB91}.

\item Brown, P.  \ref{pa-P44}.

\item Brueggemann-Klein, A.  \ref{pa-WL}.

\item Brunetti, P.  \ref{pa-QR}.

\item Cai, J.  \ref{pa-P43}.

\item Card, S.K. \ref{pa-cone}

\item Carpano, M.J.  \ref{pa-R2}, \ref{pa-ZA}.

\item Catarci, T.  \ref{pa-WH}.

\item Cederbaum, I.  \ref{pa-UB}.

\item Chiba, N.  \ref{pa-ZY}, \ref{pa-ZQ}, \ref{pa-XK}, \ref{pa-XR}, \ref{pa-XS}.

\item Chilenskas, M.  \ref{pa-RJ}.

\item Chrobak, M.  \ref{pa-WA}.

\item Cohen, R.F.  \ref{pa-P18}, \ref{pa-BCDTT94}, \ref{pa-P12}.

\item Cormen, T.H.  \ref{pa-PDE0}.

\item Cosmadakis, S.  \ref{pa-WC}.

\item Crescenzi, P.  \ref{pa-P2}.

\item Cruz, I.F.  \ref{pa-Cruz}.

\item Cuny, J.E.  \ref{pa-R7}.

\item Czyzowicz, J.  \ref{pa-YR}, \ref{pa-YS}, \ref{pa-YU},
\ref{pa-Y9}, \ref{pa-SZ}.

\item Dao, M.  \ref{pa-QI}.

\item Davidson, R.  \ref{pa-PDEq}.

\item Davis, M.  \ref{pa-R4}.

\item Deal, S. \ref{pa-Deal}.

\item Dehne, F.  \ref{pa-Sack}.

\item Delarche, M.  \ref{pa-ZA}.

\item Delott, G.  \ref{pa-P27}.

\item Dengler, E. \ref{pa-Dengler}.

\item Deo, N.  \ref{pa-SB}, \ref{pa-P23}.

\item Di Battista, G.  \ref{pa-GD93}, \ref{pa-P2}, \ref{pa-R6}, \ref{pa-PXX1}, 
\ref{pa-P5},  \ref{pa-RF}, \ref{pa-P14}, \ref{pa-P16}, \ref{pa-P42},
\ref{pa-esa}, \ref{pa-YV}, \ref{pa-P17}, \ref{pa-P18}, \ref{pa-BCDTT94},
\ref{pa-ZC}, \ref{pa-WE}, \ref{pa-SS}, \ref{pa-QQ}, \ref{pa-QR},
\ref{pa-PDEt}, \ref{pa-P10}, \ref{pa-P11}, \ref{pa-P12},
\ref{pa-RS}, \ref{pa-DV93}.

\item Di Felice, P.  \ref{pa-QG}.

\item Ding, C. \ref{pa-P7}.

\item Djidjev, H.  \ref{pa-Sack}.

\item Dolev, D.  \ref{pa-YB}.

\item Duby, C.  \ref{pa-SH}.

\item Duchet, P.  \ref{pa-YE}.

\item Eades, P.  \ref{pa-PDE1}, \ref{pa-PDE2}, \ref{pa-GD93}, \ref{pa-P1},
\ref{pa-PDE3}, \ref{pa-PDE5}, 
\ref{pa-ZO}, \ref{pa-ZV},
\ref{pa-XW}, \ref{pa-P27}, \ref{pa-QJ},
\ref{pa-PDEd}, \ref{pa-PDEe}, \ref{pa-PDEg}, \ref{pa-PDEh}, \ref{pa-ZD},
\ref{pa-PDEi}, \ref{pa-ZG}, \ref{pa-DOM4}, \ref{pa-QN},
\ref{pa-QO}, \ref{pa-PDEu}.

\item Eggleton, R.B.  \ref{pa-QA}.

\item ElGindy, H. \ref{pa-DOM4}.

\item Eppstein, D.  \ref{pa-Italiano}.

\item Esposito, C.  \ref{pa-SL}.

\item Even, S.  \ref{pa-RC}, \ref{pa-UB}, \ref{pa-UC}, \ref{pa-DOM2}.

\item Fary, I.  \ref{pa-XM}.

\item Feiner, S.K.  \ref{pa-SD}.

\item Ferrari, D.  \ref{pa-ZZ}.

\item Fogg, I.  \ref{pa-QO}.

\item Foley, J.D.  \ref{pa-SD}.

\item Formann, M.  \ref{pa-P22}.

\item Foulds, L.  \ref{pa-ZU}, \ref{pa-ZV}.

\item Fourneau, J.M.  \ref{pa-WR}.

\item Fournier, I.  \ref{pa-WR}.

\item Frank, A.  \ref{pa-PDEl}.

\item de Fraysseix, H.  \ref{pa-GD93}, \ref{pa-YD}, \ref{pa-XJ}, 
\ref{pa-XY}, \ref{pa-P19}, \ref{pa-P24}.

\item Friedell, M.  \ref{pa-RJ}, \ref{pa-R5}, \ref{pa-Dengler}.

\item Fruchterman, T. \ref{pa-P25}.

\item Fuhrman, T.E.  \ref{pa-SI}.

\item Fujimoto, H.  \ref{pa-SW}.

\item Fujisawa, T. \ref{pa-MNKF90}.

\item Furer, M.  \ref{pa-FRHK92}, \ref{pa-FRHK93}.

\item Furlani, L.  \ref{pa-ST}.

\item Gansner, E.R.  \ref{pa-SJ}, \ref{pa-P40}, \ref{pa-P46}.

\item Garey, M.R.  \ref{pa-SC}, \ref{pa-ZL}.

\item Galil, Z.  \ref{pa-Italiano}.

\item Garg, A.  \ref{pa-GGT93}, \ref{pa-GT94}.

\item Gargiulo, T.  \ref{pa-P44}.

\item Germa, A.  \ref{pa-WR}.

\item Giammarco, A.  \ref{pa-P10}.

\item Gibbons, P.B.  \ref{pa-Gib85}, \ref{pa-ZU}.

\item Giffin, J.  \ref{pa-ZU}, \ref{pa-ZV}.

\item Gilbert, R.S.  \ref{pa-KMG88}.

\item Goldschmidt, O.  \ref{pa-Takvorian}.

\item Goodrich, M.T.  \ref{pa-GGT93}, \ref{pa-Goodrich}.

\item Gregori, A.  \ref{pa-PDE6}.

\item Gschwind, D.J.  \ref{pa-SV}.

\item Guarna, V.A.  \ref{pa-SF}.

\item Guy, R.K.  \ref{pa-RZ}.

\item Habib, M.  \ref{pa-QI}.

\item Hagerman, J.W.  \ref{pa-R7}.

\item Hagerup, T.  \ref{pa-P22}.

\item Hamidoune, Y.  \ref{pa-YE}.

\item Han, X.  \ref{pa-P43}.

\item Haralambides, J.  \ref{pa-P22}.

\item Harary, F.  \ref{pa-RB}.

\item Harborth, H.  \ref{pa-RN}.

\item Harel, D. \ref{pa-PDEq}, \ref{pa-SO}.

\item He, X.  \ref{pa-PDEa}, \ref{pa-KantHe}, \ref{pa-FRHK92},
\ref{pa-FRHK93}.

\item Henry, R.H.  \ref{pa-UF}.

\item Henry, T.R.  \ref{pa-P33}.

\item Himsolt, M.  \ref{pa-RV}.

\item Hopcroft, J.  \ref{pa-XI}.

\item Hope, A.K.  \ref{pa-R8}.

\item Hornick, S.W.  \ref{pa-andersen}.

\item Horowitz, E.  \ref{pa-SA}.

\item Hotz, G.  \ref{pa-XT}.

\item Hough, A.A.  \ref{pa-R7}.

\item Houle, M.  \ref{pa-DOM4}.

\item Hudson, S.E.  \ref{pa-P33}.

\item Hughes, J.F.  \ref{pa-SD}.

\item Hutton, M.D.  \ref{pa-P15}.

\item Hynd, J.  \ref{pa-QN}.

\item Idicula, P.J.  \ref{pa-PDE7}.

\item Italiano, G.F.  \ref{pa-Italiano}.

\item Ja'Ja', J.  \ref{pa-P37}.

\item Jablonowski, D.  \ref{pa-SF}.

\item Jansen, V.  \ref{pa-P26}.

\item Jayakumar, R. \ref{pa-ZT}, \ref{pa-RU},  \ref{pa-Y3}.

\item Johnson, D.S.  \ref{pa-SC}, \ref{pa-ZJ}, \ref{pa-ZK},
\ref{pa-ZL}, \ref{pa-RO}.

\item Jones, S.  \ref{pa-P27}.

\item J\"unger, M.  \ref{pa-Mutzel}.

\item J\"urgensen, H.  \ref{pa-R9}.

\item Kajitani, Y.  \ref{pa-UG}.

\item Kamada, T.  \ref{pa-P47}, \ref{pa-WG}, \ref{pa-UA}, \ref{pa-WW},
\ref{pa-QK}.

\item Kameda T. \ref{pa-DOM1}.

\item Kant, G.  \ref{pa-P13}, \ref{pa-KA1}, \ref{pa-P34}, \ref{pa-P3}, 
\ref{pa-Kant}, \ref{pa-KLTT93}, \ref{pa-P6}, \ref{pa-KantHe}.

\item Kao, M.Y.  \ref{pa-FRHK92}, \ref{pa-FRHK93}.

\item Kar, G.  \ref{pa-KMG88}.

\item Kashiwabara, T. \ref{pa-MNKF90}.

\item Kaufmann, M.  \ref{pa-P22}.

\item Kawai, S.  \ref{pa-WG}, \ref{pa-WW}.

\item Kelly, D.  \ref{pa-YP}, \ref{pa-RE}.

\item Kelly, D.  \ref{pa-ZG}, \ref{pa-QO}.

\item Kirkpatrick, D.G.  \ref{pa-SQ}.

\item Kiyokane, Y.  \ref{pa-SW}.

\item Klein, P.N.  \ref{pa-P39}.

\item Knuth, D.E.  \ref{pa-SN}.

\item Koike, H.  \ref{pa-PDEs}.

\item Kosac, C.  \ref{pa-P28}, \ref{pa-PDEy}.

\item Koustofios, E.  \ref{pa-P40}, \ref{pa-P46}.

\item Kramer, M.R.  \ref{pa-ZM}.

\item Kramlich, D.  \ref{pa-RJ}.

\item Krull, F.N.  \ref{pa-SI}.

\item Kruskal, J.B. \ref{pa-Kru}

\item Kumar, A.  \ref{pa-QD}.

\item Laborde, J.M.  \ref{pa-Bordier}.

\item Laborie, M.  \ref{pa-RK}.

\item Lai, W.  \ref{pa-PDEu}.

\item Las Vergnas, M.  \ref{pa-YE}.

\item Lee, D.T.  \ref{pa-YC}.

\item Lehman, J.  \ref{pa-RJ}, \ref{pa-R5}.

\item Leighton, F.T.  \ref{pa-YB}, \ref{pa-P22}.

\item Leiserson, C.E.  \ref{pa-PDE0}, \ref{pa-Leiserson}.

\item Lempel, A.  \ref{pa-UB}, \ref{pa-DOM2}.

\item Lenhart, W. \ref{pa-DOM4}.

\item Lin, T.  \ref{pa-P1}, \ref{pa-PDE3}.

\item Lin, X.  \ref{pa-P1}, \ref{pa-PDE3}, \ref{pa-QJ}, \ref{pa-PDEf},
\ref{pa-PDEg}, \ref{pa-PDEh}.

\item Liotta, G.  \ref{pa-PXX1}, \ref{pa-KLTT93}, \ref{pa-P42}, \ref{pa-PDEt},
\ref{pa-P11}.

\item Lipton, R.  \ref{pa-ZN}.

\item Liu, W.P.  \ref{pa-P14}.

\item Loewer, J.  \ref{pa-R9}.

\item Lubiw, A.  \ref{pa-P15}.

\item Luccio, F.  \ref{pa-YC}, \ref{pa-YI}.

\item Lueker, G.  \ref{pa-RD}.

\item Lyons, K.  \ref{pa-PDEv}.

\item Mackinlay, J.D.  \ref{pa-cone}, \ref{pa-PDEx}.

\item Madden, B.P.  \ref{pa-KMG88}.

\item Maestrini, P.  \ref{pa-YC}.

\item Majewski, M.A.  \ref{pa-SI}.

\item M\"akinen, E.   \ref{pa-WJ}, \ref{pa-ZH}, \ref{pa-WD},
\ref{pa-P29}, \ref{pa-P30}, \ref{pa-RW}.

\item Malitz, S.  \ref{pa-P21}.

\item Manning, J.  \ref{pa-XG}, \ref{pa-XX}, \ref{pa-RX}, \ref{pa-MA1},
\ref{pa-MA2}.

\item Mannino, C.  \ref{pa-P42}, \ref{pa-esa}.

\item Marchetti,  F.E.  \ref{pa-QY}.

\item Marek-Sadowska, M.  \ref{pa-ZP}.

\item Marks, J.  \ref{pa-P28}, \ref{pa-PDEy}, \ref{pa-Marks},
\ref{pa-Dengler}.

\item Masuda, S. \ref{pa-MNKF90}.

\item Mateti, P.  \ref{pa-P7}.

\item May, M.  \ref{pa-P35}, \ref{pa-P31}.

\item Mazzone, S.  \ref{pa-YI}.

\item McHugh, J.A. \ref{pa-Mc90}

\item McKay, B.  \ref{pa-ZD}.

\item McKee, R.  \ref{pa-R5}.

\item de Mendez, P.O.  \ref{pa-P24}.

\item Mendon\c{c}a, C.X.  \ref{pa-PDEr}.

\item Mengersen, I.  \ref{pa-RN}.

\item Mennecke, P.  \ref{pa-P35}.

\item Messinger, E.  \ref{pa-R4}, \ref{pa-RT}, \ref{pa-UF}.

\item Meyer, C.  \ref{pa-R4}.

\item Meyers, S.  \ref{pa-SH}.

\item Meyniel, H.  \ref{pa-YE}.

\item Mezzalira, L.  \ref{pa-ZZ}.

\item Miller, G.L.  \ref{pa-P38}.

\item Miller, M. \ref{pa-DOM4}.

\item Miller, Z.  \ref{pa-SM}.

\item Miriyala, K.  \ref{pa-andersen}.

\item Misra, A.  \ref{pa-QD}.

\item Misue, K.  \ref{pa-PDEu}, \ref{pa-RP}.

\item Moen, S.  \ref{pa-SG}.

\item Moran, A.  \ref{pa-P27}.

\item Mostue, B.M.  \ref{pa-QL}.

\item Murtagh, T.P. \ref{pa-SV}.

\item Murty, U.  \ref{pa-RA}.

\item Mutzel, P.  \ref{pa-Mutzel}.

\item Naggar, P.  \ref{pa-QR}.

\item Nagl, M.  \ref{pa-QM}.

\item Nakajima, K. \ref{pa-MNKF90}.

\item Nakamura, K.  \ref{pa-SW}.

\item Nardelli, E. \ref{pa-ZR}, \ref{pa-QB}, \ref{pa-ZC}, \ref{pa-WE},
\ref{pa-QH}, \ref{pa-QP}, \ref{pa-QR}, \ref{pa-ST}.

\item Newbery,  F.J.  \ref{pa-P32}, \ref{pa-QT}, \ref{pa-WM},
\ref{pa-WN}, \ref{pa-PDEw}.

\item Nievergelt, J.  \ref{pa-SB}.

\item Nishioka, I.  \ref{pa-ZQ}.

\item Nishizeki, I.  \ref{pa-ZY}, \ref{pa-XK}, \ref{pa-XR},
\ref{pa-XS}.

\item North, S.C.  \ref{pa-ZN}, \ref{pa-SJ}, \ref{pa-P40}, \ref{pa-P46}.

\item Nummenmaa, J.  \ref{pa-N92}, \ref{pa-P9}.

\item Onoguchi, K.  \ref{pa-XS}.

\item Orlin. J.B.  \ref{pa-SM}.

\item Osthof, H.G.  \ref{pa-XU}.

\item Otten, R.H.J.M.  \ref{pa-YJ}.

\item Ozawa, T.  \ref{pa-ZS}, \ref{pa-XK}, \ref{pa-YM}.

\item Pach, J.  \ref{pa-XY}, \ref{pa-P19}.

\item Papakostas, A.  \ref{pa-P21}.

\item Pato, J.  \ref{pa-WU}.

\item Payne, T.H. \ref{pa-WA}.

\item Pelc, A.  \ref{pa-YR}, \ref{pa-YS}, \ref{pa-YT}, \ref{pa-SZ}.

\item Pietrosanti, E.  \ref{pa-SS}.

\item Piperno, A.  \ref{pa-P2}.

\item Platt, C.  \ref{pa-YQ}.

\item Pnueli, A. \ref{pa-DOM2}.

\item Pollack, R.  \ref{pa-XY}, \ref{pa-P19}.

\item Pollak, H.O.  \ref{pa-RO}.

\item Potthoff, A.  \ref{pa-P26}.

\item Preparata, F.P.  \ref{pa-SE}.

\item Protsko, L.B.  \ref{pa-P8}.

\item Rademacher, H.  \ref{pa-WT}.

\item Raghavachari, B.  \ref{pa-FRHK92}, \ref{pa-FRHK93}.

\item Ramachandran, V.  \ref{pa-WP}, \ref{pa-P36}.

\item Rappaport, D. \ref{pa-DOM4}.

\item Read, R.  \ref{pa-XV}, \ref{pa-QS}.

\item Reggiani,  M.G.  \ref{pa-QY}.

\item Reif, J.H.  \ref{pa-WP}, \ref{pa-P36}, \ref{pa-P38}, \ref{pa-P39}.

\item Reiner, D.  \ref{pa-RJ}, \ref{pa-R5}, \ref{pa-QE}.

\item Reingold, E.  \ref{pa-SB}, \ref{pa-XD}, \ref{pa-XF}, \ref{pa-P25}.

\item Reiss, S.  \ref{pa-WU}, \ref{pa-WV}, \ref{pa-SH}, \ref{pa-Reiss}.

\item Rheingans, P.  \ref{pa-R5}.

\item Richard, J.  \ref{pa-QI}.

\item Richelli, G.  \ref{pa-QR}.

\item Rival, I.  \ref{pa-SY}, \ref{pa-YR}, \ref{pa-YS}, \ref{pa-YT},
\ref{pa-SZ}, \ref{pa-SX}, \ref{pa-RL}, \ref{pa-rival93}, \ref{pa-YP},
\ref{pa-P14}.

\item Rivest, R.L.  \ref{pa-PDE0}.

\item Robertson, G.G. \ref{pa-cone}.

\item Robins, G.  \ref{pa-WO}.

\item Rosenstiehl, P.  \ref{pa-GD93}, \ref{pa-YD}, \ref{pa-XJ}, \ref{pa-YK},
\ref{pa-P24}, \ref{pa-P41}.

\item Rosenthal, A.  \ref{pa-RJ}, \ref{pa-R5}.

\item Rowe, L.A.  \ref{pa-R4}, \ref{pa-UF}.

\item Rudich, A.  \ref{pa-Dror}.

\item Sack, J.-R.  \ref{pa-Sack}.

\item Sahni, S.  \ref{pa-SA}, \ref{pa-QW}.

\item Saint-Paul, A.  \ref{pa-RK}.

\item Sandberg, J.  \ref{pa-ZN}.

\item Santucci, G.  \ref{pa-P10}.

\item Sarkar, M. \ref{pa-SB91}.

\item Savage, J.E.  \ref{pa-QU}.

\item Schaefer, D.A.  \ref{pa-P8}.

\item Schlag, M.  \ref{pa-YC}.

\item Schnyder, W.  \ref{pa-WK}.

\item Seery, J.B. \ref{pa-Kru}

\item Shamos, M.I.  \ref{pa-SE}.

\item Shannon, A.  \ref{pa-XB}.

\item Shannon, G.  \ref{pa-UD}.

\item Sherlekar, D.  \ref{pa-Sherlekar}.

\item Shieber, S.  \ref{pa-PDEy}.

\item Shiloach, Y.  \ref{pa-UE}.

\item Shirakawa, I.  \ref{pa-ZQ}.

\item Shor, P.  \ref{pa-PDEm}.

\item Simon, J.  \ref{pa-P37}.

\item Simvonis, T.  \ref{pa-P22}.

\item Skiena, S., \ref{pa-Skiena}

\item Smart, J.C.  \ref{pa-P45}.

\item Sorenson, P.G.  \ref{pa-P8}.

\item Sotteau, D.  \ref{pa-WR}.

\item Spencer, T.H.  \ref{pa-Italiano}.

\item Spirakis, C.  \ref{pa-R4}.

\item Steadman,  J.P.  \ref{pa-YN}.

\item Stein, S.K.  \ref{pa-XN}.

\item Steinitz, E.  \ref{pa-WT}.

\item Storer, J.A.  \ref{pa-R1}.

\item Strani, M.  \ref{pa-PDEt}.

\item Sugiyama, K.  \ref{pa-R3}, \ref{pa-YZ}, \ref{pa-WF}, \ref{pa-PDEd},
\ref{pa-ZB}, \ref{pa-ZI}, \ref{pa-PDEu}, \ref{pa-RP}.

\item Supowit, K.  \ref{pa-XF}.

\item Suzuki, T.  \ref{pa-SW}.

\item Swaminathan, V.  \ref{pa-QD}.

\item Swamy, M.N.S.  \ref{pa-ZT}, \ref{pa-RU}, \ref{pa-Y3}.

\item Sweet, R.E.  \ref{pa-XA}.

\item Szkatula, K.  \ref{pa-P31}.

\item Tagawa, S.  \ref{pa-R3}.

\item Takahashi, H.  \ref{pa-ZS}, \ref{pa-UG}.

\item Takvorian, A.  \ref{pa-Takvorian}.

\item Talamo, M.  \ref{pa-ZR}, \ref{pa-QB}, \ref{pa-QF}, \ref{pa-QP}.

\item Tallot, D.  \ref{pa-QI}.

\item Tamassia, R.  \ref{pa-PDE1}, \ref{pa-PDE2}, \ref{pa-GD93},
\ref{pa-GGT93}, \ref{pa-QB}, \ref{pa-R6}, \ref{pa-P27}, \ref{pa-XZ},
\ref{pa-RH}, \ref{pa-WB}, \ref{pa-TTV91}, \ref{pa-TTV291}, \ref{pa-P4},
\ref{pa-TT87}, \ref{pa-YH}, \ref{pa-YL},  \ref{pa-P5}, \ref{pa-KLTT93},
\ref{pa-SR}, \ref{pa-RF}, \ref{pa-esa}, \ref{pa-TAJC90}, \ref{pa-YV},
\ref{pa-P17}, \ref{pa-P18}, \ref{pa-BCDTT94}, \ref{pa-PDEh},
\ref{pa-QC}, \ref{pa-SS}, \ref{pa-QF}, \ref{pa-QG}, \ref{pa-QH},
\ref{pa-QP}, \ref{pa-QQ}, \ref{pa-QR}, \ref{pa-P10}, \ref{pa-TV89},
\ref{pa-WQ}, \ref{pa-P12}, \ref{pa-RS}, \ref{pa-andersen},
\ref{pa-Cruz}, \ref{pa-GT94}.

\item Tarjan, R.E.  \ref{pa-ZX}, \ref{pa-P43}, \ref{pa-XH}, \ref{pa-XI}, 
\ref{pa-UC}, \ref{pa-YK}.

\item Tarui, Y.  \ref{pa-SW}.

\item Thomas, W.  \ref{pa-P26}.

\item Thomassen, C.  \ref{pa-XQ}, \ref{pa-YF}, \ref{pa-SU}.

\item Thulasiraman, K.  \ref{pa-ZT}, \ref{pa-RU}, \ref{pa-Y3}.

\item Tichy,  W.F.  \ref{pa-QT}, \ref{pa-WN}.

\item Tilford, J.  \ref{pa-XD}, \ref{pa-XE}.

\item Toda, M. \ref{pa-R3}, \ref{pa-YZ}.

\item Tollis, I.G.  \ref{pa-RH}, \ref{pa-WB}, \ref{pa-TTV91},
\ref{pa-TTV291}, \ref{pa-TT87}, \ref{pa-YH}, \ref{pa-YL}, \ref{pa-P5},
\ref{pa-KLTT93}, \ref{pa-SR},  \ref{pa-YV}, \ref{pa-P17}, \ref{pa-P18},
\ref{pa-BCDTT94}, \ref{pa-SS}, \ref{pa-P12}.

\item Tremblay, J.P.  \ref{pa-P8}.

\item Trickey, H.   \ref{pa-WS}, \ref{pa-YB}.

\item Tuan, A.  \ref{pa-R4}.

\item Tunkelang, D. \ref{pa-Tun92}.

\item Tuomi, J.  \ref{pa-P9}.

\item Tutte, W.T. \ref{pa-XO}, \ref{pa-XP}.

\item Urrutia, J.  \ref{pa-YS}.

\item Valiant, L.  \ref{pa-YA}.

\item van Dam, A.  \ref{pa-SD}.

\item Van Hentenryck, P.  \ref{pa-Cruz}.

\item van Leeuwen, J.  \ref{pa-ZM}.

\item van Wijk, J.G.  \ref{pa-YJ}.

\item Vargiu, F.  \ref{pa-PXX1}, \ref{pa-PDEt}.

\item Vaucher, J.  \ref{pa-XC}.

\item Vemuri, V.  \ref{pa-P45}.

\item Vijayan, G.  \ref{pa-VW85}, \ref{pa-P20}.

\item Vismara, L. \ref{pa-DV93}.

\item Vitter, J.S.  \ref{pa-TTV91},
\ref{pa-TTV291}, \ref{pa-TV89}, \ref{pa-WQ}.

\item Vo, K.P.  \ref{pa-SJ}, \ref{pa-P40}, \ref{pa-P46}.

\item Wagner, K.  \ref{pa-XL}.

\item Walker II, J.Q. \ref{pa-W90}.

\item Ward, N.  \ref{pa-P27}.

\item Warfield, J.  \ref{pa-ZF}.

\item Watanabe,  H.  \ref{pa-QZ}.

\item Welzl, E.  \ref{pa-P22}.

\item Wermuth, U.  \ref{pa-P26}.

\item Wetherell, C.  \ref{pa-XB}.

\item Whitesides, S. \ref{pa-DOM4}.

\item Wigderson, A.  \ref{pa-VW85}.

\item Wille, R.  \ref{pa-SY}.

\item Wismath, S.  \ref{pa-YG}, \ref{pa-SQ}.

\item Woeginger, G.  \ref{pa-P22}.

\item Wong, C.K.  \ref{pa-YC}, \ref{pa-YI}.

\item Wood, D.  \ref{pa-WL}.

\item Woods, D.  \ref{pa-RI}.

\item Wormald, N.  \ref{pa-XW}, \ref{pa-ZD}, \ref{pa-PDEi}.

\item Yamanouchi, T.  \ref{pa-XR}.

\item Yannakakis, M. \ref{pa-DOM3}.

\item Zernik, D.  \ref{pa-Dror}.

\item Zischler, H.  \ref{pa-QM}.

\item Zodik, G.  \ref{pa-Dror}.

\end{description}

\clearpage
%
\onecolumn

% -------------------------------------------------------------------

\end{document}

%% -------------------------------------------------------------------
