\begin{thebibliography}{GKNV93}

\bibitem[CG72]{CG72}
E.~G. Coffman and R.~L. Graham.
\newblock Optimal scheduling for two processor systems.
\newblock {\em Acta Informatica}, 1:200--213, 1972.

\bibitem[CK93]{ck-cgd3c-93}
M.~Chrobak and G.~Kant.
\newblock Convex grid drawings of 3-connected planar graphs.
\newblock Technical {Report} RUU-93-45, Dept. of Computer Sci., Utrecht Univ.,
  1993.

\bibitem[CK97]{CK97}
M.~Chrobak and G.~Kant.
\newblock Convex grid drawings of 3-connected planar graphs.
\newblock {\em Interntl. Journal on Computational Geometry and Applications},
  7(3):211--224, 1997.

\bibitem[DETT99]{DETT99}
G.~{Di Battista}, P.~Eades, R.~Tamassia, and I.G. Tollis.
\newblock {\em Graph Drawing}.
\newblock Prentice Hall, 1999.

\bibitem[DPP90]{dpp-hdpgg-90}
H.~{De Fraysseix}, J.~Pach, and R.~Pollack.
\newblock How to draw a planar graph on a grid.
\newblock {\em Combinatorica}, 10(1):41--51, 1990.

\bibitem[DT96a]{BT96b}
G.~{Di Battista} and R.~Tamassia.
\newblock On-line maintanance of triconnected components with spqr-trees.
\newblock {\em Algorithmica}, 15:302--318, 1996.

\bibitem[DT96b]{BT96a}
G.~{Di Battista} and R.~Tamassia.
\newblock On-line planarity testing.
\newblock {\em SIAM J. Comput.}, 25(5):956--997, 1996.

\bibitem[EK86]{EK86}
P.~Eades and D.~Kelly.
\newblock Heuristics for reducing crossings in 2-layered networks.
\newblock {\em Ars Combinatoria}, 21(A):89--98, 1986.

\bibitem[EL95]{EL95}
P.~Eades and X.~Lin.
\newblock A new heuristic for the feedback arc set problem.
\newblock {\em Australian Journal of Combinatorics}, 12:15--26, 1995.

\bibitem[EW86]{EW86}
P.~Eades and N.~Wormald.
\newblock The median heuristic for drawing 2-layers networks.
\newblock Technical Report~69, Department of Computer Science, University of
  Queensland, 1986.

\bibitem[Fia97]{Fialko97}
S.~Fialko.
\newblock Das planare {A}ugmentierungsproblem.
\newblock {D}iplomarbeit, Universit{\"a}t des {S}aarlandes, Saarbr{\"u}cken,
  1997.

\bibitem[FM98]{FM98}
S.~Fialko and P.~Mutzel.
\newblock A new approximation algorithm for the planar augmentation problem.
\newblock In {\em Proceedings of the Ninth Annual ACM-SIAM Symposium on
  Discrete Algorithms (SODA '98)}, pages 260--269, San Francisco, California,
  1998. ACM Press.

\bibitem[FR91]{fr-gdfdp-91}
T.~Fruchterman and E.~Reingold.
\newblock Graph drawing by force-directed placement.
\newblock {\em Softw. -- Pract. Exp.}, 21(11):1129--1164, 1991.

\bibitem[GJR84]{GJR84}
M.~Gr{\"o}tschel, M.~J{\"u}nger, and G.~Reinelt.
\newblock A cutting plane algorithm for the linear ordering problem.
\newblock {\em Operations Research}, 32:1159--1220, 1984.

\bibitem[GJR85]{GJR85}
M.~Gr{\"o}tschel, M.~J{\"u}nger, and G.~Reinelt.
\newblock On the acyclic subgraph polytope.
\newblock {\em Mathematical Programming}, 33:28--42, 1985.

\bibitem[GKNV93]{GKNV93}
E.~R. Gansner, E.~Koutsofios, S.~C. North, and K.~P. Vo.
\newblock A technique for drawing directed graphs.
\newblock {\em IEEE Trans. Softw. Eng.}, 19(3):214--230, 1993.

\bibitem[GM97]{GM97}
C.~Gutwenger and P.~Mutzel.
\newblock Grid embedding of biconnected planar graphs.
\newblock Extended Abstract, Max-Planck-Institut f{\"u}r Informatik,
  Saarbr{\"u}cken, Germany, 1997.

\bibitem[GM98]{GM98b}
C.~Gutwenger and P.~Mutzel.
\newblock Planar polyline drawings with good angular resolution.
\newblock In S.~Whitesides, editor, {\em Graph Drawing (Proc. GD '98)}, volume
  1547 of {\em Lecture Notes in Computer Science}, pages 167--182.
  Springer-Verlag, 1998.

\bibitem[Him97]{H97}
M.~Himsolt.
\newblock The {G}raphlet system.
\newblock {\em Proc.~Graph Drawing '96, LNCS}, 1190:233--240, 1997.
\newblock See also
  \htmladdnormallink{\texttt{http://www.uni-passau.de/Graphlet} }{
  http://www.uni-passau.de/Graphlet}.

\bibitem[HT73]{HT73}
J.~E. Hopcroft and R.~E. Tarjan.
\newblock Dividing a graph into triconnected components.
\newblock {\em SIAM J. Comput.}, 2(3):135--158, 1973.

\bibitem[JLM96]{JLM96}
M.~J\"unger, S.~Leipert, and P.~Mutzel.
\newblock On computing a maximal planar subgraph using {PQ}--trees.
\newblock Technical Report 96.227, Institut f\"ur Informatik, Universit\"at zu
  K\"oln, 1996.

\bibitem[JLM97]{JLM97}
M.~J{\"u}nger, S.~Leipert, and P.~Mutzel.
\newblock Pitfalls of using {PQ}-trees in automatic graph drawing.
\newblock In G.~Di~Battista, editor, {\em Graph Drawing (Proc. GD '97)}, volume
  1353 of {\em Lecture Notes in Computer Science}, pages 193--204.
  Springer-Verlag, 1997.

\bibitem[JLM98]{JLM98b}
M.~J{\"u}nger, S.~Leipert, and P.~Mutzel.
\newblock A note on computing a maximal planar subgraph using pq-trees.
\newblock {\em IEEE Transactions on Computer-Aided Design}, 1998.
\newblock to appear.

\bibitem[JM94]{JM95}
M.~J\"unger and P.~Mutzel.
\newblock The polyhedral approach to the maximum planar subgraph problem: New
  chances for related problems.
\newblock In {\em DIMACS Graph Drawing '94}, volume 894 of {\em LNCS}, pages
  119--130. Springer-Verlag, 1994.

\bibitem[JM96]{JM96a}
M.~J{\"u}nger and P.~Mutzel.
\newblock Maximum planar subgraphs and nice embeddings: Practical layout tools.
\newblock {\em Algorithmica, Special Issue on Graph Drawing}, 16(1):33--59,
  1996.

\bibitem[JT97]{JT97}
M.~J{\"u}nger and S.~Thienel.
\newblock The design of the branch and cut system \uppercase{ABACUS}.
\newblock Technical Report No.~97.260, Institut f\"ur Informatik, Universit\"at
  zu K\"oln, 1997.
\newblock See also
  \htmladdnormallink{\texttt{http://www.informatik.uni-koeln.de/ls\_juenger/pr%
ojects/abacus.html} }{
  http://www.informatik.uni-koeln.de/ls\_juenger/projects/abacus.html}.

\bibitem[JTS89]{JTS89}
R.~Jayakumar, K.~Thulasiramans, and M.N.S. Swamy.
\newblock On {$(n^2)$}algorithms for graph planarization.
\newblock {\em Transactions on Computer-Aided Design}, 8(3):257--267, March
  1989.

\bibitem[Kan96]{Kan96}
G.~Kant.
\newblock Drawing planar graphs using the canonical ordering.
\newblock {\em Algorithmica, Special Issue on Graph Drawing}, 16(1):4--32,
  1996.

\bibitem[Kla97]{Klau97}
G.~Klau.
\newblock Quasi-orthogonales {Z}eichnen planarer {G}raphen mit wenigen
  {K}nicken.
\newblock {D}iplomarbeit, Max-Planck-Institut f{\"u}r Informatik,
  Saarbr{\"u}cken, Germany, 1997.

\bibitem[KM98a]{KM98b}
G.~W. Klau and P.~Mutzel.
\newblock Optimal compaction of orthogonal grid drawings.
\newblock Technical report, Max--Planck--Institut f{\"u}r Informatik,
  Saarbr{\"u}cken, December 1998.

\bibitem[KM98b]{KM98}
G.~W. Klau and P.~Mutzel.
\newblock Quasi--orthogonal drawing of planar graphs.
\newblock Technical Report MPI-I-98-1-013, Max--Planck--Institut f{\"u}r
  Informatik, Saarbr{\"u}cken, 1998.

\bibitem[Lei95]{Lei95}
S.~Leipert.
\newblock {B}erechnung maximal planarer {U}ntergraphen mit {H}ilfe von
  {PQ}-{B}{\"a}umen.
\newblock {D}iplomarbeit, Institut f{\"u}r Informatik, Universit{\"a}t zu
  K{\"o}ln, 1995.

\bibitem[Lei96]{Lei96}
S.~Leipert.
\newblock The tree interface - version 1.0 user manual.
\newblock Technical Report No.~96.242, Institut f{\"u}r Informatik,
  Universit{\"a}t zu K{\"o}ln, 1996.

\bibitem[LS77]{LS77}
S.~Lam and R.~Sethi.
\newblock Worst case analysis of two scheduling algorithms.
\newblock {\em SIAM J. Comput.}, 6(3):518--536, 1977.

\bibitem[MN95]{Mehlhorn-Naeher:CACM}
K.~Mehlhorn and S.~N{\"a}her.
\newblock \uppercase{LEDA}: A platform for combinatorial and geometric
  computing.
\newblock {\em Comm.~Assoc.~Comput.~Mach.}, 38:96--102, 1995.

\bibitem[MNSU99]{LEDA-Manual}
K.~Mehlhorn, S.~N{\"a}her, M.~Seel, and Ch. Uhrig.
\newblock {\em The {L}{E}{D}{A} {U}ser {M}anual ({V}ersion {R} 3.8)}, 1999.
\newblock Max-Planck-Institut f{\"u}r Informatik, Saarbr{\"u}cken, Germany. See
  also \htmladdnormallink{\texttt{http://www.mpi-sb.mpg.de/LEDA/leda.html} }{
  http://www.mpi-sb.mpg.de/LEDA/leda.html}.

\bibitem[MSM00]{MSM99}
C.~Matuszewski, R.~Sch{\"o}nfeld, and P.~Molitor.
\newblock Using sifting for k-layer crossing minimization.
\newblock In {\em Graph Drawing (Proc. GD '99)}, Lecture Notes in Computer
  Science. Springer-Verlag, 2000.
\newblock to appear.

\bibitem[Mut94]{Mut94}
P.~Mutzel.
\newblock {\em The maximum planar subgraph problem}.
\newblock PhD thesis, Institut f{\"u}r Informatik, Universit{\"a}t zu K{\"o}ln,
  1994.

\bibitem[Mut95]{Mut95}
P.~Mutzel.
\newblock A polyhedral approach to planar augmentation and related problems.
\newblock In Paul Spirakis, editor, {\em Annual European Symposium on
  Algorithms (ESA-3) : Corfu, Greece, September 2 5-27, 1995; proceedings},
  volume LNCS 979, pages 494--507, Berlin, 1995. Springer.

\bibitem[Pur97]{Pur97}
H.~Purchase.
\newblock Which aesthetic has the greatest effect on human understanding?
\newblock In G.~Di~Battista, editor, {\em Graph Drawing (Proc. GD '97)}, volume
  1353 of {\em Lecture Notes in Computer Science}, pages 248--261.
  Springer-Verlag, 1997.

\bibitem[RT81]{rt-tdt-81}
E.~Reingold and J.~Tilford.
\newblock Tidier drawing of trees.
\newblock {\em IEEE Trans. Softw. Eng.}, SE-7(2):223--228, 1981.

\bibitem[RT86]{rt-rplbo-86}
P.~Rosenstiehl and R.~E. Tarjan.
\newblock Rectilinear planar layouts and bipolar orientations of planar graphs.
\newblock {\em Discrete Comput. Geom.}, 1(4):343--353, 1986.

\bibitem[Rud93]{Rud93}
R.~Rudell.
\newblock Dynamic variable ordering for ordered binary decision diagrams.
\newblock In {\em Proc.\ International Conf.\ on Computer-Aided Design
  (ICCAD)}, pages 42--47, 1993.

\bibitem[Sch90]{s-epgg-90}
W.~Schnyder.
\newblock Embedding planar graphs on the grid.
\newblock In {\em Proc. 1st ACM-SIAM Sympos. Discrete Algorithms}, pages
  138--148, 1990.

\bibitem[STT81]{stt-mvuhs-81}
K.~Sugiyama, S.~Tagawa, and M.~Toda.
\newblock Methods for visual understanding of hierarchical systems.
\newblock {\em IEEE Trans. Syst. Man Cybern.}, SMC-11(2):109--125, 1981.

\bibitem[Tam87]{t-eggmn-87}
R.~Tamassia.
\newblock On embedding a graph in the grid with the minimum number of bends.
\newblock {\em SIAM J. Comput.}, 16(3):421--444, 1987.

\bibitem[Tut63]{t-hdg-63}
W.~T. Tutte.
\newblock How to draw a graph.
\newblock {\em Proceedings London Mathematical Society}, 13(3):743--768, 1963.

\bibitem[{Wal}90]{w-npagt-90}
J.~Q. {Walker II}.
\newblock A node-positioning algorithm for general trees.
\newblock {\em Softw. -- Pract. Exp.}, 20(7):685--705, 1990.

\end{thebibliography}
