Graph separators, with applications (Q2748499)

This book appeared in the edition ``Frontiers of Computer Science'' and quite corresponds to the goal of that edition. It presents some concepts of the graph theory and then their applications in the computer science. The most important application is in the construction of VLSI-circuits (Very Large Scale Integrated circuits). But there are also other applications described.NEWLINENEWLINENEWLINEThe first chapter is ``A Technical Introduction''. It explains basic concepts of the graph theory and presents some graph families which are interesting from the viewpoint of the topic of the book. The principal concept of the book follows, namely the graph separator. It is a set of vertices or a set of edges whose removal divides the graph into two or more disjoint subgraphs. Some ``variations on the theme'' are presented mainly the graph embeddings. (At those embeddings an edge may be transformed into a path of length greater than one.)NEWLINENEWLINENEWLINEIn the second chapter applications are described. As it was mentioned, the most important application is laying out VLSI-circuits. Other applications are the so-called nonserial dynamic programming, graph embeddings via separators, strongly universal interval hypergraphs and pebbling games. To separators and their variants always some numerical values are related and they should be maximized or minimized. This is the content of the third chapter ``Upper-Bound Techniques'' and of the fourth chapter ``Lower-Bound Techniques''. At the end Appendix A is added; in it the authors return to the topis of the second chapter and apply the content of the third and the fourth chapter in them.NEWLINENEWLINENEWLINEThe book may be recommended mainly to computer scientists; to them it brings information about graph theory concepts which can be theoretical source of applications. Among graph theorists the book will be helpful mainly for those who study and use graph algorithms.