Mathematical Reviews: MR1712180 (2001i:05001)  Ehrenfeucht, A.; Harju, T.; Rozenberg, G. The theory of 2-structures. A framework for decomposition and transformation of graphs. World Scientific Publishing Co., Inc., River Edge, NJ, 1999. xvi+290 pp. ISBN: 981-02-4042-2 Classification: 05-02 (05C15 05C20 68R10) A 2-structure (or unlabelled 2-structure) g = (D, R) consists of a finite non-empty set D of vertices, and an equivalence relation R on the set (D ×D) - {(x,x) : x Î D}. Put differently, a 2-structure consists of a symmetric complete digraph with vertex set D and a colouring of its arcs, two 2-structures with the same vertex set being regarded as equal if and only if they differ by a permutation of the colours. In a labelled 2-structure the names of the colours assigned to the arcs are important. Two labelled 2-structures g1 and g2 on the same vertex set are different if and only of some arc has a different colour in g1 than in g2. To quote from the preface: "Much of the motivation for the research presented in this book comes from the area of graph grammars, where one considers the global effect of local transformations defined through grammatical productions. We believe that (especially the dynamic part of) the theory of 2-structures enriches the study of graph grammars by making available the tools from group theory and the theory of switching." Indeed, the presentation often has a strong algebraic flavour and the many results closely resemble those in universal algebra. The book is comprised of 15 chapters, which fall into four categories: preliminary notions, unlabelled 2-structures, labelled 2-structures, and local transformations (Seidel switchings). It represents a cohesive presentation of a large body of research due to the authors, sometimes in collaboration with others. The preliminary concepts, introduced in the first two chapters, include equivalence relations, partial orders, semigroups, and monoids in Chapter 1, and graph-theoretic notions, including comparability graphs, permutation graphs, and cographs and their construction trees, in Chapter 2. Unlabelled 2-structures are studied in Chapters 3 through 7. A key concept is that of a clan, a subset X of vertices of the 2-structure which all "look the same" to each vertex not in X. Basic properties of clans are studied in Chapter 3. Homomorphisms and their relationship with clans are studied in Chapter 4. The main result in the fifth chapter is the clan decomposition theorem. For undirected graphs this is known in the literature as the modular decomposition. It is also shown in this chapter that every 2-structure can be represented by a special construction tree. Chapters 6 and 7 discuss 2-structures which are primitive (have no nontrivial clans), and angular (very roughly speaking, highly imprimitive), respectively. In Chapters 8 through 10 many of the results from the preceding chapters are modified and presented for labelled 2-structures. Automorphisms of labelled 2-structures are considered in Chapter 10. One of the main results states that for any finite group G there is a labelled 2-structure whose automorphism group is G. Finally, Chapters 11 through 15 discuss (Seidel) switchings of directed and undirected graphs, and labelled 2-structures. From Chapter 12 onwards, the results concern switchings of 2-structures in which the labels on the edges come from a group. Topics studied include cardinalities of switching classes, and invariants of switching classes. It is the connection with algebra that, for me, gives the book its greatest strength and contributes to its greatest weakness. There is a lot of interesting material. I am impressed by the amount of detail that has been included and the completeness of the theory presented. The authors have drawn together concepts from algebra, ordered sets, graph theory, Seidel switching and more. If one invests the time to carefully study the book, then there is a lot to learn, and one will be much richer for having made the effort. On the other hand, for someone not working in this exact area, it would be difficult to use this book as a reference. The volume of definitions, some of which look familiar but may not mean what one expects, makes it hard to pick up the book and scan for results. I think that this could be a wonderful book to use for a graduate course if the students were already familiar with the vast majority of the topics covered in the first two chapters, and had a reasonable background in algebra. I enjoyed reading it, and at times found it to be harder work than I had anticipated. Reviewer: Gary MacGillivray File translated from TEX by TTH, version 2.92. On 2 Dec 2004, 16:25.