| 1991 | A Generalized Encryption Scheme Based on Random Graphs. | Ludek Kucera |
| 1991 | Fast Parallel Algorithms for Coloring Random Graphs. | Zvi M. Kedem, Krishna V. Palem, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis |
| 1991 | Optimal Vertex Ordering of a Graph and its Application to Symmetry Detection. | Xiaoyi Jiang, Horst Bunke |
| 1991 | The Complexity of Approximating the Class Steiner Tree Problem. | Edmund Ihler |
| 1991 | Optimal Embedding of Complete Binary Trees into Lines and Grids. | Ralf Heckmann, Ralf Klasing, Burkhard Monien, Walter Unger |
| 1991 | Voronoi Diagrams of Moving Points in the Plane. | Leonidas J. Guibas, Joseph S. B. Mitchell |
| 1991 | Attributed Elementary Programmed Graph Grammars. | Rudolf Freund, Brigitte Haberstroh |
| 1991 | Dynamic Algorithms for Shortest Paths in Planar Graphs. | Esteban Feuerstein, Alberto Marchetti-Spaccamela |
| 1991 | Line Digraph Iterations and Spread Concept - with Application to Graph Theory, Fault Tolerance, and Routing. | Ding-Zhu Du, Yuh-Dauh Lyuu, D. Frank Hsu |
| 1991 | Logic Arrays for Interval Indicator Functions. | Peter Damaschke |
| 1991 | Tight Bounds for the Rectangualr Art Gallery Problem. | Jurek Czyzowicz, Eduardo Rivera-Campo, Nicola Santoro, Jorge Urrutia, Joseph Zaks |
| 1991 | Monadic Second-Order Evaluations on Tree-Decomposable Graphs. | Bruno Courcelle, Mohamed Mosbah |
| 1991 | Short Disjoint Cycles in Cubic Bridgeless Graphs. | Andreas Brandstdt |
| 1991 | Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height. | Hans L. Bodlaender, John R. Gilbert, Ton Kloks, Hjlmtyr Hafsteinsson |
| 1991 | On Disjoint Cycles. | Hans L. Bodlaender |
| 1991 | A Language for Generic Graph-Transformations. | Marc Andries, Jan Paredaens |
| 1990 | Embeddings of Treelike Graphs into 2-Dimensional Meshes. | Peter Zienicke |
| 1990 | Comparing the expressibility of two languages formed using NP-complete graph operators. | Iain A. Stewart |
| 1990 | On Feedback Problems in Planar Digraphs. | Hermann Stamm |
| 1990 | Decomposition of Linear Recursive Logic Programs. | Dietmar Seipel |
| 1990 | Genus of Order and Lattices. | Klaus Reuter, Ivan Rival |
| 1990 | Finding Minimally Weighted Subgraphs. | Jrgen Plehn, Bernd Voigt |
| 1990 | Optimal Parallel Algorithms for Sparse Graphs. | Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis |
| 1990 | Avoiding Matrix Multiplication. | Tze-Heng Ma, Jeremy P. Spinrad |
| 1990 | Approximating the minimum net expansion: Near optimal solutions to circuit partitioning problems. | Fillia Makedon, Spyros Tragoudas |