Rectilinear planar layouts and bipolar orientations of planar graphs

K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity usingPQ-tree algorithms,J. Comput. System Sci. 13 (1976), 335–379.

M. H. Brown and R. Sedgewick, A system for algorithm animation, Technical Report No. CS-84-01, Department of Computer Science, Brown University, Providence, RI, 1984.

N. Chiba, T. Yamanouchi, and T. Nishizeki, Linear algorithms for convex drawings of planar graphs,Proceedings of the Silver Jubilee Conference on Combinatorics, 1982, University of Waterloo, Waterloo, Ontario, to appear.

R. Cori and J. Hardouin-Duparc, Manipulation des cartes planaires à partir de leur codage, Département de Mathématiques, Université de Bordeaux, Talence, France, 1975.

P. Duchet, Y. Hamidoune, M. Las Vergnas, and H. Meyniel, Representing a planar graph by vertical lines joining different intervals,Discrete Math. 46 (1983), 319–321.

J. Ebert,st-ordering the vertices of biconnected graphs,Computing 30 (1983), 19–33.

S. Even and R. E. Tarjan, Computing anst-numbering,Theoret. Comput. Sci. 2 (1976), 339–344.

I. Fáry, On straight line representing of planar graphs,Acta. Sci. Math. (Szeged)11 (1948), 229–233.

H. de Fraysseix, Drawing planar and non-planar graphs from the half-edge code, to appear.

H. de Fraysseix and P. Rosenstiehl, Structures combinatoires pour des traćes automatiques de réseaux,Proceedings of the Third European Conference on CAD/CAM and Computer Graphics, 332–337, 1984.

H. de Fraysseix and P. Rosenstiehl, L'algorithme gauche-droite pour le plongement des graphes dans le plan, to appear.

D. H. Greene, Efficient coding and drawing of planar graphs, Xerox Palo Alto Research Center, Palo Alto, CA, 1983.

J. Hopcroft and R. Tarjan, Efficient planarity testing,J. Comput. Mach. 21 (1974), 549–568.

D. E. Knuth,The Art of Computer Programming, Vol. 1, 2nd ed., 258–265, Addison-Wesley, Reading, MA, 1973.

A. Lempel, S. Even, and I. Cederbaum, An algorithm for planarity testing of graphs,Theory of Graphs (International Symposium, Rome, July 1966) (P. Rosenstiehl, ed.), 215–232, Gordon and Breach, New York, 1967.

C. Mead and L. Conway,Introduction to VLSI Systems, Addison-Wesley, Reading, MA, 1980.

R. H. J. M. Otten and J. G. van Wijk, Graph representations in interactive layout design,Proceedings of the IEEE International Symposium on Circuits and Systems 914–918, 1978.

P. Rosenstiehl, Embedding in the plane with orientation constraints,Ann. N.Y. Acad. Sci., to appear.

Y. Shiloach, Arrangement of planar graphs on the planar lattice, Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel, 1976.

R. Tamassia and I. G. Tollis, Algorithms for visibility representations of planar graphs, Coordinated Science Laboratory, University of Illinois, Urbana, IL, 1985.

R. E. Tarjan, Finding dominators in directed graphs,SIAM J. Comput. 3 (1974), 62–69.

R. E. Tarjan, Two streamlined depth-first search algorithms,Fund. Inform.,IX (1986), 85–94.

W. T. Tutte, How to draw a graph,Proc. London Math. Soc. 13 (1963), 743–768.

D. R. Woods, Drawing planar graphs, Report No. STAN-CS-82-943, Computer Science Department, Stanford University, Stanford, CA, 1981.