Bibliography

CG72

E. G. Coffman and R. L. Graham.
Optimal scheduling for two processor systems.
Acta Informatica, 1:200-213, 1972.

CK93

M. Chrobak and G. Kant.
Convex grid drawings of 3-connected planar graphs.
Technical Report RUU-93-45, Dept. of Computer Sci., Utrecht Univ., 1993.

CK97

M. Chrobak and G. Kant.
Convex grid drawings of 3-connected planar graphs.
Interntl. Journal on Computational Geometry and Applications, 7(3):211-224, 1997.

DETT99

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis.
Graph Drawing.
Prentice Hall, 1999.

DPP90

H. De Fraysseix, J. Pach, and R. Pollack.
How to draw a planar graph on a grid.
Combinatorica, 10(1):41-51, 1990.

DT96a

G. Di Battista and R. Tamassia.
On-line maintanance of triconnected components with spqr-trees.
Algorithmica, 15:302-318, 1996.

DT96b

G. Di Battista and R. Tamassia.
On-line planarity testing.
SIAM J. Comput., 25(5):956-997, 1996.

EK86

P. Eades and D. Kelly.
Heuristics for reducing crossings in 2-layered networks.
Ars Combinatoria, 21(A):89-98, 1986.

EL95

P. Eades and X. Lin.
A new heuristic for the feedback arc set problem.
Australian Journal of Combinatorics, 12:15-26, 1995.

EW86

P. Eades and N. Wormald.
The median heuristic for drawing 2-layers networks.
Technical Report 69, Department of Computer Science, University of Queensland, 1986.

Fia97

S. Fialko.
Das planare Augmentierungsproblem.
Diplomarbeit, Universität des Saarlandes, Saarbrücken, 1997.

FM98

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

FR91

T. Fruchterman and E. Reingold.
Graph drawing by force-directed placement.
Softw. - Pract. Exp., 21(11):1129-1164, 1991.

GJR84

M. Grötschel, M. Jünger, and G. Reinelt.
A cutting plane algorithm for the linear ordering problem.
Operations Research, 32:1159-1220, 1984.

GJR85

M. Grötschel, M. Jünger, and G. Reinelt.
On the acyclic subgraph polytope.
Mathematical Programming, 33:28-42, 1985.

GKNV93

E. R. Gansner, E. Koutsofios, S. C. North, and K. P. Vo.
A technique for drawing directed graphs.
IEEE Trans. Softw. Eng., 19(3):214-230, 1993.

GM97

C. Gutwenger and P. Mutzel.
Grid embedding of biconnected planar graphs.
Extended Abstract, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1997.

GM98

C. Gutwenger and P. Mutzel.
Planar polyline drawings with good angular resolution.
In S. Whitesides, editor, Graph Drawing (Proc. GD '98), volume 1547 of Lecture Notes in Computer Science, pages 167-182. Springer-Verlag, 1998.

Him97

M. Himsolt.
The Graphlet system.
Proc. Graph Drawing '96, LNCS, 1190:233-240, 1997.
See also http://www.uni-passau.de/Graphlet .

HT73

J. E. Hopcroft and R. E. Tarjan.
Dividing a graph into triconnected components.
SIAM J. Comput., 2(3):135-158, 1973.

JLM96

M. Jünger, S. Leipert, and P. Mutzel.
On computing a maximal planar subgraph using PQ-trees.
Technical Report 96.227, Institut für Informatik, Universität zu Köln, 1996.

JLM97

M. Jünger, S. Leipert, and P. Mutzel.
Pitfalls of using PQ-trees in automatic graph drawing.
In G. Di Battista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes in Computer Science, pages 193-204. Springer-Verlag, 1997.

JLM98

M. Jünger, S. Leipert, and P. Mutzel.
A note on computing a maximal planar subgraph using pq-trees.
IEEE Transactions on Computer-Aided Design, 1998.
to appear.

JM94

M. Jünger and P. Mutzel.
The polyhedral approach to the maximum planar subgraph problem: New chances for related problems.
In DIMACS Graph Drawing '94, volume 894 of LNCS, pages 119-130. Springer-Verlag, 1994.

JM96

M. Jünger and P. Mutzel.
Maximum planar subgraphs and nice embeddings: Practical layout tools.
Algorithmica, Special Issue on Graph Drawing, 16(1):33-59, 1996.

JT97

M. Jünger and S. Thienel.
The design of the branch and cut system ABACUS.
Technical Report No. 97.260, Institut für Informatik, Universität zu Köln, 1997.
See also http://www.informatik.uni-koeln.de/ls_juenger/pr ojects/abacus.html .

JTS89

R. Jayakumar, K. Thulasiramans, and M.N.S. Swamy.
On (n²)algorithms for graph planarization.
Transactions on Computer-Aided Design, 8(3):257-267, March 1989.

Kan96

G. Kant.
Drawing planar graphs using the canonical ordering.
Algorithmica, Special Issue on Graph Drawing, 16(1):4-32, 1996.

Kla97

G. Klau.
Quasi-orthogonales Zeichnen planarer Graphen mit wenigen Knicken.
Diplomarbeit, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1997.

KM98a

G. W. Klau and P. Mutzel.
Optimal compaction of orthogonal grid drawings.
Technical report, Max-Planck-Institut für Informatik, Saarbrücken, December 1998.

KM98b

G. W. Klau and P. Mutzel.
Quasi-orthogonal drawing of planar graphs.
Technical Report MPI-I-98-1-013, Max-Planck-Institut für Informatik, Saarbrücken, 1998.

Lei95

S. Leipert.
Berechnung maximal planarer Untergraphen mit Hilfe von PQ-Bäumen.
Diplomarbeit, Institut für Informatik, Universität zu Köln, 1995.

Lei96

S. Leipert.
The tree interface - version 1.0 user manual.
Technical Report No. 96.242, Institut für Informatik, Universität zu Köln, 1996.

LS77

S. Lam and R. Sethi.
Worst case analysis of two scheduling algorithms.
SIAM J. Comput., 6(3):518-536, 1977.

MN95

K. Mehlhorn and S. Näher.
LEDA: A platform for combinatorial and geometric computing.
Comm. Assoc. Comput. Mach., 38:96-102, 1995.

MNSU99

K. Mehlhorn, S. Näher, M. Seel, and Ch. Uhrig.
The LEDA User Manual (Version R 3.8), 1999.
Max-Planck-Institut für Informatik, Saarbrücken, Germany. See also http://www.mpi-sb.mpg.de/LEDA/leda.html .

MSM00

C. Matuszewski, R. Schönfeld, and P. Molitor.
Using sifting for k-layer crossing minimization.
In Graph Drawing (Proc. GD '99), Lecture Notes in Computer Science. Springer-Verlag, 2000.
to appear.

Mut94

P. Mutzel.
The maximum planar subgraph problem.
PhD thesis, Institut für Informatik, Universität zu Köln, 1994.

Mut95

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

Pur97

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

RT81

E. Reingold and J. Tilford.
Tidier drawing of trees.
IEEE Trans. Softw. Eng., SE-7(2):223-228, 1981.

RT86

P. Rosenstiehl and R. E. Tarjan.
Rectilinear planar layouts and bipolar orientations of planar graphs.
Discrete Comput. Geom., 1(4):343-353, 1986.

Rud93

R. Rudell.
Dynamic variable ordering for ordered binary decision diagrams.
In Proc. International Conf. on Computer-Aided Design (ICCAD), pages 42-47, 1993.

Sch90

W. Schnyder.
Embedding planar graphs on the grid.
In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138-148, 1990.

STT81

K. Sugiyama, S. Tagawa, and M. Toda.
Methods for visual understanding of hierarchical systems.
IEEE Trans. Syst. Man Cybern., SMC-11(2):109-125, 1981.

Tam87

R. Tamassia.
On embedding a graph in the grid with the minimum number of bends.
SIAM J. Comput., 16(3):421-444, 1987.

Tut63

W. T. Tutte.
How to draw a graph.
Proceedings London Mathematical Society, 13(3):743-768, 1963.

Wal90

J. Q. Walker II.
A node-positioning algorithm for general trees.
Softw. - Pract. Exp., 20(7):685-705, 1990.