## Efficient Graph Representations.: The Fields Institute for Research in Mathematical Sciences. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

Implicit Representation | 17 |

Intersection and Containment Representations | 31 |

Real Numbers in Graph Representations | 53 |

Classes Which use Global Information | 59 |

Visibility Graphs | 73 |

Intersection of Graph Classes | 85 |

Graph Classes Defined by Forbidden Subgraphs | 97 |

Elimination Schemes | 181 |

Recognition Algorithms | 191 |

Robust Algorithms for Optimization Problems | 231 |

Characterization and Construction | 257 |

Applications | 265 |

Glossary | 277 |

Survey of Results on Graph Classes | 303 |

319 | |

### Other editions - View all

### Common terms and phrases

adjacency list adjacency matrix bound boxicity chapter chordal bipartite graphs chordal comparability graphs chordal graphs chordless cycle circle graph circular-arc graphs class of graphs classes defined clique cover clique problem clique separator clique-width co-comparability graphs cographs color class column comparability graph complement computing construct corresponding cycle of length decomposable decomposition tree dimension dominating set edge endpoints entries exercise F-free graph classes graph G graph recognition graphs of paths implicit representation induced subgraph intersection graphs interval graphs interval number join decomposition matrix multiplication maximum clique module neighbors node nonadjacent nonneighbors NP-complete number of graphs O(n+m O(nlogn Open Problem pair of vertices path graphs perfect elimination scheme perfect graphs permutation graphs polygon polynomial poset proof recognition algorithm robust algorithm Show skew partition solved split graphs stored strongly chordal graphs subset substitution decomposition theorem tolerance graphs transitive orientation trapezoid graphs treewidth unit disk graphs visibility graph weakly chordal graphs

### Popular passages

Page 11 - A graph is an interval graph if one can associate with each vertex an interval on the real line such that two vertices are adjacent if and only if the corresponding intervals have a nonempty intersection.

Page 331 - A linear time algorithm for deciding interval graph isomorphism, Journal of the ACM, 26 (1979), 183-195.