| 1998 | A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking. Hajo Broersma, Ton Kloks, Dieter Kratsch, Haiko Müller |
| 1998 | A Linear-Time Algorithm to Find Four Independent Spanning Trees in Four-Connected Planar Graphs. Kazuyuki Miura, Daishiro Takahashi, Shin-Ichi Nakano, Takao Nishizeki |
| 1998 | A Polynomial-Time Algorithm for Finding Total Colorings of Partial k-Trees. Shuji Isobe, Xiao Zhou, Takao Nishizeki |
| 1998 | An Estimate of the Tree-Width of a Planar Graph Which Has Not a Given Planar Grid as a Minor. Konstantin Yu. Gorbunov |
| 1998 | Broadcasting on Anonymous Unoriented Tori. Stefan Dobrev, Peter Ruzicka |
| 1998 | Communication in the Two-Way Listen-in Vertex-disjoint Paths Mode. Hans-Joachim Böckenhauer |
| 1998 | Compact Implicit Representation of Graphs. Maurizio Talamo, Paola Vocca |
| 1998 | Diameter Determination on Restricted Graph Faminlies. Derek G. Corneil, Feodor F. Dragan, Michel Habib, Christophe Paul |
| 1998 | Domination and Steiner Tree Problems on Graphs with Few P4S. Luitpold Babel, Stephan Olariu |
| 1998 | Drawing Planar Partitions II: HH-Drawings. Therese Biedl, Michael Kaufmann, Petra Mutzel |
| 1998 | Efficient Embeddings of Grids into Grids. Markus Röttger, Ulf-Peter Schroeder |
| 1998 | Families of Graphs Having Broadcasting and Gossiping Properties. Guillaume Fertin, André Raspaud |
| 1998 | Graph-Theoretic Concepts in Computer Science, 24th International Workshop, WG '98, Smolenice Castle, Slovak Republic, June 18-20, 1998, Proceedings Juraj Hromkovic, Ondrej Sýkora |
| 1998 | Graphs with Bounded Induced Distance. Serafino Cicerone, Gabriele Di Stefano |
| 1998 | Improved Compressions of Cube-Connected Cycles Networks. Ralf Klasing |
| 1998 | Independent Tree Spanners. Dagmar Handke |
| 1998 | Integral Uniform Flows in Symmetric Networks. Farhad Shahrokhi, László A. Székely |
| 1998 | Interally Typed Second-Order Term Graphs. Wolfram Kahl |
| 1998 | Interval Completion with the Smallest Max-degree. Fedor V. Fomin, Petr A. Golovach |
| 1998 | Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases. Koichi Wada, Wei Chen |
| 1998 | Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width. Bruno Courcelle, Johann A. Makowsky, Udi Rotics |
| 1998 | Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs. Elias Dahlhaus |
| 1998 | Minus Domination in Small-Degree Graphs. Peter Damaschke |
| 1998 | Optical All-to-All Communication in Inflated Networks. Olivier Togni |
| 1998 | Rankings of Directed Graphs. Jan Kratochvíl, Zsolt Tuza |
| 1998 | Routing in Recursive Circulant Graphs: Edge Forwarding Index and Hamiltonian Decomposition. Ginette Gauyacq, C. Micheneau, André Raspaud |
| 1998 | Splitting Number is NP-complete Luérbio Faria, Celina M. H. de Figueiredo, Candido Ferreira Xavier de Mendonça Neto |
| 1998 | The Vertex-Disjoint Triangles Problem. Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong |
| 1998 | Tree Spanners in Planar Graphs. Sándor P. Fekete, Jana Kremer |
| 1998 | Triangles in Euclidean Arrangements. Stefan Felsner, Klaus Kriegel |
| 1998 | Upgrading Bottleneck Constrained Forests. Sven Oliver Krumke, Madhav V. Marathe, Hartmut Noltemeier, S. S. Ravi, Hans-Christoph Wirth |