| 1995 | A Compact Data Structure and Parallel Algorithms for Permutation Graphs. Jens Gustedt, Michel Morvan, Laurent Viennot |
| 1995 | A Dynamic Algorithm for Line Graph Recognition. Daniele Giorgio Degiorgi, Klaus Simon |
| 1995 | A Uniform Approach to Graph Rewriting: The Pullback Approach. Michel Bauderon |
| 1995 | An Approximation Algorithm for 3-Colourability. Ingo Schiermeyer |
| 1995 | Chordal Graphs and Their Clique Graphs. Philippe Galinier, Michel Habib, Christophe Paul |
| 1995 | Complexity and Approximability of Certain Bicriteria Location Problems. Sven Oliver Krumke, Hartmut Noltemeier, S. S. Ravi, Madhav V. Marathe |
| 1995 | Diametral Path Graphs. Jitender S. Deogun, Dieter Kratsch |
| 1995 | Efficient Parallel Modular Decomposition (Extended Abstract). Elias Dahlhaus |
| 1995 | Finding and Counting Small Induced Subgraphs Efficiently. Ton Kloks, Dieter Kratsch, Haiko Müller |
| 1995 | Graph-Theoretic Concepts in Computer Science, 21st International Workshop, WG '95, Aachen, Germany, June 20-22, 1995, Proceedings Manfred Nagl |
| 1995 | Graph-Theoretical Methods to Construct Entity-Relationship Databases. Sven Hartmann |
| 1995 | Highly Fault-Tolerant Routings and Diameter Vulnerability for Generalized Hypercube Graphs. Koichi Wada, Takaharu Ikeo, Kimio Kawaguchi, Wei Chen |
| 1995 | Homogeneously Orderable Graphs and the Steiner Tree Problem. Andreas Brandstädt, Feodor F. Dragan, Falk Nicolai |
| 1995 | Hot-Potato Routing on Multi-Dimensional Tori. Friedhelm Meyer auf der Heide, Matthias Westermann |
| 1995 | Incremental Hive Graph. Fabrizio d'Amore, Roberto Giaccio |
| 1995 | Modular Decomposition of Hypergraphs. Paola Bonizzoni, Gianluca Della Vedova |
| 1995 | NC Algorithms for Partitioning Planar Graphs into Induced Forests and Approximating NP-Hard Problems. Zhi-Zhong Chen, Xin He |
| 1995 | Non-Oblivious Local Search for Grpah and Hyperpraph Coloring Problems. Paola Alimonti |
| 1995 | On Devising Boolean Routing Schemes. Michele Flammini, Giorgio Gambosi, Sandro Salomone |
| 1995 | On Interval Routing Schemes and Treewidth. Hans L. Bodlaender, Richard B. Tan, Dimitrios M. Thilikos, Jan van Leeuwen |
| 1995 | On Termination of Graph Rewriting. Detlef Plump |
| 1995 | On the Isomorphism of Graphs with Few P4s. Luitpold Babel, Stephan Olariu |
| 1995 | Optimal Cutwidths and Bisection Widths of 2- and 3-Dimensional Meshes. José D. P. Rolim, Ondrej Sýkora, Imrich Vrto |
| 1995 | Partition Coefficients of Acyclic Graphs. John L. Pfaltz |
| 1995 | Planarization of Graphs Embedded on Surfaces. Hristo N. Djidjev, Shankar M. Venkatesan |
| 1995 | Searching for Faulty Leaves in Binary Trees. Peter Damaschke |
| 1995 | Sub-Cubic Cost Algorithms for the All Pairs Shortest Path Problem. Tadao Takaoka |
| 1995 | The Malleability of TSP_{2Opt}. Sophie Fischer, Leen Torenvliet |
| 1995 | Toward a General Theory of Unicast-Based Multicast Communication. Barbara D. Birchler, Abdol-Hossein Esfahanian, Eric Torng |
| 1995 | VC-Dimensions for Graphs (Extended Abstract). Evangelos Kranakis, Danny Krizanc, Berthold Ruf, Jorge Urrutia, Gerhard J. Woeginger |
| 1995 | Visualizing Two- and Three-Dimensional Models of Meristematic Growth. F. David Fracchia |