16:00-20:00 Registration 16:15 Departure of the conference bus (or a car) from the Bratislava airport 17:15 Departure of the conference bus from Bratislava bus station 17:45 Departure of the conference bus from Bratislava railway station 18:45 Expected arrival of the conference bus at the Smolenice Castle 20:00 Welcome party

8:30 Opening of the conference 9:00-10:30 Session I Chair: A. Brandstaedt 9:00 Linear Time Solvable Optimization Problems on Certain Structured Graph Families B. Courcelle, J. A. Makowsky, U. Rotics 9:30 Minus Domination in Small-Degree Graphs P. Damaschke 10:00 The Vertex-Disjoint Triangles Problem V. Guruswami, C. P. Rangan, M.S. Chang, G.J. Chang, C.K. Wong 10:30-11:00 Coffee Break 11:00-13:00 Session II Chair: P. Widmayer 11:00 Communication in the Two-way Listen-in Vertex-disjoint Paths Mode H.-J. Boeckenhauer 11:30 Broadcasting on Anonymous Unoriented Torus S. Dobrev, P. Ruzicka 12:00 Families of Graphs having Broadcasting and Gossiping Properties G. Fertin, A. Raspaud 12:30 Optical All-to-All Communication in Inflated Networks O. Togni 13:00-15:00 Lunch break 15:00-16:30 Session III Chair: H. Bodlaender 15:00 A generalization of AT-free graphs and a generic algorithm for solving treewidth, minimum fill-in and vertex ranking H. Broersma, T. Kloks, D. Kratsch, H. Muller 15:30 A Polynomial-Time Algorithm for Finding Total Colorings of Partial k-Tress S. Isobe, X. Zhou, T. Nishizeki 16:00 Ranking of Directed Graphs J. Kratochvil, Z. Tuza 16:30-17:00 Coffee break 17:00-19:00 Session IV Chair: D. Wagner 17:00 Drawing Planar Partitions II: HH-Drawings T. Biedl, M. Kaufmann, P. Mutzel 17:30 Triangles in Euclidean Arrangements S. Felsner, K. Kriegel 18:00 Internally Typed Second-Order Term Graphs W. Kahl 18:30 Almost Optimal Implicit Representation of Graphs M. Talamo, P. Vocca 19:00-20:00 Dinner 20:00 Meeting of the WG'98 program committee

7:45- 8:30 Breakfast 8:30-10:30 Session V Chair: R. Moehring 8:30 Graphs with Bounded Induced Distance S. Cicerone, G. Di Stefano 9:00 Diameter Determination on Restricted Graph Families D. G. Corneil, F. F. Dragan, M. Habib, C. Paul 9:30 Independent Tree Spanners: Fault-Tolerant Spanning Trees with Constant Distance Guarantees D. Handke 10:00 Upgrading Bottleneck Constrained Forests S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi, H. C. Wirth 10:30-11:00 Coffee break 11:00-13:00 Session VI Chair: M. Nagl 11:00 Routing in Recursive Circulant Graphs: Edge Forwarding Index and Hamiltonian Decomposition G. Guayacq, C. Micheneau, A. Raspaud 11:30 Improved Compressions of Cube-Connected Cycles Networks R. Klasing 12:00 Efficient Embedding of Grids into Grids M. Rottger, U.-P. Schroeder 12:30 Integer Uniform Flows in Symmetric Networks F. Shahrokhi, L. A. Szekely 13:00-14:00 Lunch 14:00-17:00 Social events 17:30-18:50 Poster and demo session Chair: L. Kucera 17:30 Deletion in Closure Spaces J. Pfaltz 17:45 On-line coloring of oriented graphs L. Vignal 18:00 Demonstration of HOPS (Visual programming with strongly Typed Term Graphs) W. Kahl 18:30 Demonstration of shortest route calculations U. Lauther 19:30 Conference dinner (picnic like - outdoors - depends on the weather)

7:45-8:30 Breakfast 8:30-10:30 Session VII Chair: M. Habib 8:30 Splitting Number is NP-complete L. Faria, C. M. H. de Figueiredo, C. F. X. Mendonca 9:00 Tree Spanners in Planar Graphs S. P. Fekete, J. Kremer 9:30 A Linear-Time Algorithm to Find Four Independent Spanning Trees in Four-Connected Planar Graphs K. Miura, D. Takahashi, S. Nakano, T. Nishizeki 10:00 Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases K. Wada, W. Chen 10:30-11:00 Coffee break 11:00-13:00 Session VIII Chair: G. Tinhofer 11:00 Domination and Steiner Tree Problems on Graphs with Few P_4s L. Babel, S. Olariu 11:30 Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs E. Dahlhaus 12:00 Interval completion with the smallest max-degree F. V. Fomin, P. A. Golovach 12:30 An estimate of the tree-width of a graph which has not a given planar grid as a minor K. Y. Gorbunov 13:00-14:00 Lunch 14:00 Expected departure of the conference bus from the Smolenice Castle