DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME NINE
TITLE: "PLANAR GRAPHS"
EDITORS: William T. Trotter
Published by the American Mathematical Society

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.

PREFACE

During the 1991/92 academic year, Fan R.K. Chung and I served as Co-Directors of the Special Year on Graph Theory and Algorithms sponsored by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS). Based on informal feedback from some of the more than 300 researchers who traveled to New Jersey this past year to participate in DIMACS activities, the Special Year was a great success. This admittedly biased view is supported by the growing list of accomplishments in which researchers recognize the role played by DIMACS in initiating, fostering and facilitating their work.

The Special Year on Graph Theory and Algorithms featured four workshops:

This monograph consists of research articles and extended abstracts submitted by participants in the Workshop on Planar Graphs. More than 70 persons attended this Workshop, and these papers cover a wide range of topics including: enumeration, characterization problems, algorithms, extremal problems, network flows and geometry.

I would like to express my appreciation to the persons who attended the Planar Graphs Workshop and contributed to its success. Also, special thanks to the authors of the articles appearing in this volume and to the many anonymous referees for their assistance with the composition of a volume which will (hopefully) have lasting scientific value. Finally, thanks to Christine Thivierge, Donna Harmon and Nancy Gerstl for their editorial and secretarial assistance.

TABLE OF CONTENTS



Forward								ix

Preface								xi

Cycles, Cocycles and Diagonals: A Characterization of 
   Planar Graphs
	Dan Archdeacon, C.P. Bonnington and C.H.C. Little	1

Stack and Queue Layouts of Directed Planar Graphs
	Lenwood S. Heath, Sriram V. Pemmaraju and Ann Trenk	5

Enumeration of Degree Restricted Rooted Maps on the Sphere
	E.A. Bender and E.R. Canfield				13

A Generalisation of MacLane's Theorem to 3-graphs
	C. Paul Bonnington and Charles H.C. Little		17

Chordal Completions of Grids and Planar Graphs
	F.R.K. Chung and David Mumford				37

Upward Planar Drawing of Single Source Acyclic Digraphs
	Michael D. Hutton and Anna Lubiw			41

Flow in Planar Graphs: A Survey of Results
	Samir Khuller and Joseph (Seffi) Naor			59

Planar Graph Coloring with an Uncooperative Partner
	H.A. Kierstead and W. T. Trotter			85

Partitioning a Rectangle into Many Sub-rectangles
  so that a Line can Meet only a Few
	Daniel J. Kleitman					95

Disjoint Essential Circuits in Toroidal Maps
	Bojan Mohar and Neil Robertson				109

Layout of Rooted Trees
	Janos Pach and Jeno Torocsik				131

Vertex Degrees in Planar Graphs
	Douglas B. West and Tood Will				139

List of Participants						151
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.