Graph-Theoretic Concepts in Computer Science: 25th International Workshop, WG’99 Ascona, Switzerland, June 17–19, 1999 Proceedings

Silver Graphs: Achievements and New Challenges....Pages 1-9
Online Algorithms: A Study of Graph-Theoretic Concepts....Pages 10-26
Discrete Optimization Methods for Packing Problems in Two and Three Dimensions — With Applications in the Textile and Car Manufacturing Industries....Pages 27-28
Informatica, Scuola, Communità: Uno Sguardo dall’ Occhio del Ciclone....Pages 29-29
Proximity-Preserving Labeling Schemes and Their Applications....Pages 30-41
Euler Is Standing in Line....Pages 42-54
Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2....Pages 55-64
Complexity Classification of Some Edge Modification Problems....Pages 65-77
On Minimum Diameter Spanning Trees under Reload Costs....Pages 78-89
Induced Matchings in Regular Graphs and Trees....Pages 89-101
Mod-2 Independence and Domination in Graphs....Pages 101-109
NLC 2 -Decomposition in Polynomial Time....Pages 110-121
On the Nature of Structure and Its Identification....Pages 122-134
On the Clique—Width of Perfect Graph Classes....Pages 135-147
An Improved Algorithm for Finding Tree Decompositions of Small Width....Pages 148-154
Efficient Analy sis of Graphs with Small Minimal Separators....Pages 155-166
Generating All the Minimal Separators of a Graph....Pages 167-172
Two Broadcasting Problems in FaultyHypercubes....Pages 173-178
Routing Permutations in the Hypercube....Pages 179-190
An Optimal Fault-Tolerant Routing for Triconnected Planar Graphs....Pages 191-201
Optimal Irreversible Dy namos in Chordal Rings....Pages 202-213
Recognizing Bipartite Incident-Graphs of Circulant Digraphs....Pages 215-227
Optimal Cuts for Powers of the Petersen Graph....Pages 228-239
Dihamiltonian Decomposition of Regular Graphs with Degree Three....Pages 240-249
Box-Rectangular Drawings of Plane Graphs....Pages 250-261
A Multi-Scale Algorithm for Drawing Graphs Nicely....Pages 262-277
All Separating Triangles in a Plane Graph Can Be Optimally “Broken” in Poly nomial Time....Pages 278-290
Linear Orderings of Random Geometric Graphs....Pages 291-302
Finding Smallest Supertrees Under Minor Containment....Pages 303-312
Vertex Cover: Further Observations and Further Improvements....Pages 313-324
On the Hardness of Recognizing Bundles in Time Table Graphs....Pages 325-337
Optimal Solutions for Frequency Assignment Problems via Tree Decomposition....Pages 338-350
Fixed-Parameter Complexity of λ-Labelings....Pages 350-363
Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)—Free Graphs....Pages 364-376
On Claw-Free Asteroidal Triple-Free Graphs....Pages 377-390
Vertex Partitioning of Crown-Free Interval Graphs....Pages 391-401
Triangulated Neighbourhoods in C 4 -Free Berge Graphs....Pages 402-412