This book contains research articles and extended abstracts submitted by participants in the Planar Graphs Workshop held at DIMACS in November 1991, one of four workshops held during the DIMACS Special Year on Graph Theory and Algorithms. With more than seventy participants, the workshop drew many of the top experts in this area. The book covers a wide range of topics, including enumeration, characterization problems, algorithms, extremal problems, and network flows and geometry.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1-7 were co-published with the Association for Computer Machinery (ACM).

Readership

Research mathematicians.

Table of Contents

• D. Archdeacon, C. P. Bonnington, and C. H. C. Little -- Cycles, cocycles and diagonals: A characterization of planar graphs
• L. S. Heath, S. V. Pemmaraju, and A. Trenk -- Stack and queue layouts of directed planar graphs
• E. A. Bender and E. R. Canfield -- Enumeration of degree restricted rooted maps on the sphere
• C. P. Bonnington and C. H. C. Little -- A generalisation of MacLane's theorem to 3-graphs
• F. R. K. Chung and D. Mumford -- Chordal completions of grids and planar graphs
• M. D. Hutton and A. Lubiw -- Upward planar drawing of single source acyclic digraphs
• S. Khuller and J. Naor -- Flow in planar graphs: A survey of results
• H. A. Kierstead and W. T. Trotter -- Planar graph coloring with an uncooperative partner
• D. J. Kleitman -- Partitioning a rectangle into many sub-rectangles so that a line can meet only a few
• B. Mohar and N. Robertson -- Disjoint essential circuits in toroidal maps
• J. Pach and J. Törőcsik -- Layout of rooted trees
• D. B. West and T. Will -- Vertex degrees in planar graphs