| 1998 | Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases. | Koichi Wada, Wei Chen |
| 1998 | Optical All-to-All Communication in Inflated Networks. | Olivier Togni |
| 1998 | Compact Implicit Representation of Graphs. | Maurizio Talamo, Paola Vocca |
| 1998 | Integral Uniform Flows in Symmetric Networks. | Farhad Shahrokhi, Lszl A. Szkely |
| 1998 | Efficient Embeddings of Grids into Grids. | Markus Rttger, Ulf-Peter Schroeder |
| 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 | Upgrading Bottleneck Constrained Forests. | Sven Oliver Krumke, Madhav V. Marathe, Hartmut Noltemeier, S. S. Ravi, Hans-Christoph Wirth |
| 1998 | Rankings of Directed Graphs. | Jan Kratochvl, Zsolt Tuza |
| 1998 | Improved Compressions of Cube-Connected Cycles Networks. | Ralf Klasing |
| 1998 | Interally Typed Second-Order Term Graphs. | Wolfram Kahl |
| 1998 | A Polynomial-Time Algorithm for Finding Total Colorings of Partial k-Trees. | Shuji Isobe, Xiao Zhou, Takao Nishizeki |
| 1998 | Independent Tree Spanners. | Dagmar Handke |
| 1998 | The Vertex-Disjoint Triangles Problem. | Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong |
| 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 | Routing in Recursive Circulant Graphs: Edge Forwarding Index and Hamiltonian Decomposition. | Ginette Gauyacq, C. Micheneau, Andr Raspaud |
| 1998 | Interval Completion with the Smallest Max-degree. | Fedor V. Fomin, Petr A. Golovach |
| 1998 | Families of Graphs Having Broadcasting and Gossiping Properties. | Guillaume Fertin, Andr Raspaud |
| 1998 | Triangles in Euclidean Arrangements. | Stefan Felsner, Klaus Kriegel |
| 1998 | Tree Spanners in Planar Graphs. | Sndor P. Fekete, Jana Kremer |
| 1998 | Splitting Number is NP-complete | Lurbio Faria, Celina M. H. de Figueiredo, Candido Ferreira Xavier de Mendona Neto |
| 1998 | Broadcasting on Anonymous Unoriented Tori. | Stefan Dobrev, Peter Ruzicka |
| 1998 | Minus Domination in Small-Degree Graphs. | Peter Damaschke |
| 1998 | Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs. | Elias Dahlhaus |
| 1998 | Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width. | Bruno Courcelle, Johann A. Makowsky, Udi Rotics |
| 1998 | Diameter Determination on Restricted Graph Faminlies. | Derek G. Corneil, Feodor F. Dragan, Michel Habib, Christophe Paul |