**Fields Institute Monographs**

Volume: 19;
2003;
342 pp;

MSC: Primary 05; 68;

**Electronic ISBN: 978-1-4704-3146-4
Product Code: FIM/19.E**

List Price: $105.00

AMS Member Price: $84.00

MAA Member Price: $94.50

#### Supplemental Materials

# Efficient Graph Representations

Share this page
*Jeremy P. Spinrad*

A co-publication of the AMS and Fields Institute

This monograph is the first to deal with graph representation as a field
of study. It is written from both a mathematical and computer science
perspective. Synthesizing the two traditions opens a number of interesting new
research areas. Some individual classes of graphs are important but are not
adequately covered in any current text. This book gives a much more current
view of important algorithmic developments in intersection graph classes than
is currently available and includes a large number of new open problems.

It deals with the questions that arise from storing a graph in a computer.
Different classes of graphs admit different forms of computer representations,
and focusing on the representations gives a new perspective on a number of
problems. For a variety of classes of graphs, the book considers such questions
as existence of good representations, algorithms for finding representations,
questions of characterizations in terms of representation, and how the
representation affects the complexity of optimization problems. General models
of efficient computer representations are also considered.

The book is designed to be used both as a text for a graduate course on
topics related to graph representation and as a monograph for anyone interested
in research in the field of graph representation. The material is of interest
both to those focusing purely on graph theory and to those working in the area
of graph algorithms.

Titles in this series are co-published with The Fields Institute for Research in Mathematical Sciences (Toronto, Ontario, Canada).

#### Reviews & Endorsements

This book presents a fantastic encyclopedia of graph classes ...

-- EMS Newsletter

The author's ‘Survey of results on graph classes’ … It is worth reading and mentions some interesting research problems … an excellent research monograph that offers plenty of material … The large number of exercises will be very helpful in teaching … highly recommended by the reviewer.

-- Mathematical Reviews

#### Table of Contents

# Table of Contents

## Efficient Graph Representations

- Cover Cover11
- Title page iii4
- Contents v6
- Explanatory remarks 110
- Introduction 514
- Implicit representation 1726
- Intersection and containment representations 3140
- Real numbers in graph representations 5362
- Classes which use global information 5968
- Visibility graphs 7382
- Intersection of graph classes 8594
- Graph classes defined by forbidden subgraphs 97106
- Chordal bipartite graphs 111120
- Matrices 135144
- Decomposition 149158
- Elimination schemes 181190
- Recognition algorithms 191200
- Robust algorithms for optimization problems 231240
- Characterization and construction 257266
- Applications 265274
- Glossary 277286
- Survey of results on graph classes 303312
- Bibliography 319328
- Index 337346
- Back Cover Back Cover1353