## Graph Separators, with ApplicationsGraph Separators with Applications is devoted to techniques for obtaining upper and lower bounds on the sizes of graph separators - upper bounds being obtained via decomposition algorithms. The book surveys the main approaches to obtaining good graph separations, while the main focus of the book is on techniques for deriving lower bounds on the sizes of graph separators. This asymmetry in focus reflects our perception that the work on upper bounds, or algorithms, for graph separation is much better represented in the standard theory literature than is the work on lower bounds, which we perceive as being much more scattered throughout the literature on application areas. Given the multitude of notions of graph separator that have been developed and studied over the past (roughly) three decades, there is a need for a central, theory-oriented repository for the mass of results. The need is absolutely critical in the area of lower-bound techniques for graph separators, since these techniques have virtually never appeared in articles having the word `separator' or any of its near-synonyms in the title. Graph Separators with Applications fills this need. |

### What people are saying - Write a review

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

### Contents

A Technical Introduction | 1 |

12 Basic Notions and Notation | 2 |

13 Interesting Graph Families | 4 |

14 Graph Separators | 12 |

15 Graph Embeddings | 27 |

16 QuasiIsometric Graph Families | 33 |

17 Sources | 44 |

Applications of Graph Separators | 47 |

35 Network Flow Approaches to Graph Separation | 130 |

36 Heuristic Approaches to Graph Separation | 147 |

37 Sources | 156 |

LowerBound Techniques | 159 |

42 Packing Arguments for Bounding SeparationWidth | 162 |

43 Congestion Arguments for Bounding SeparationWidth | 188 |

44 A Technique for Complete Trees | 209 |

45 InformationTransfer Arguments | 218 |

22 Nonserial Dynamic Programming | 49 |

23 Graph Embeddings via Separators | 53 |

24 Laying Out VLSI Circuits | 68 |

25 Strongly Universal Interval Hypergraphs | 82 |

Register Allocation and Processor Scheduling | 92 |

27 Sources | 94 |

UpperBound Techniques | 99 |

32 NPCompleteness | 101 |

33 Topological Approaches to Graph Separation | 109 |

34 Geometric Approaches to Graph Separation | 121 |

46 Sources | 223 |

Applications of Graph Separators Revisited | 227 |

A3 Laying Out VLSI Circuits | 232 |

A4 Strongly Universal Interval Hypergraphs | 235 |

A5 Pebbling Games | 239 |

A6 Sources | 240 |

241 | |

About the Authors | 251 |

253 | |

### Common terms and phrases

2SAT algorithm applications arbitrary bisection bisection-width bisector bit-position boolean hypercube Bruijn graph bucket tree butterfly graph Chapter circuit complete binary tree complete bipartite graph computational congestion arguments contains cross edge cube-connected cycles cycle cycles graph decomposition tree denote dilation edge-separator edge-weighting embed families of graphs Figure focus graph embeddings graph families graph g graph separators guest graph heuristic host graph hyperedges I-hypergraph induced subgraph inequality input nodes integer interleaving Leiserson Lemma lower bounds lower-bound techniques M-separation mincing network flow node-separator node-set notion NP-complete NP-hard number of edges number of nodes obtain optimal order-n output nodes packing arguments packing function pair of nodes partition path pebble game permutation planar graph problem proof Proposition PWL string quasi-isometry reader recursive Rosenberg routing Section 4.2 separation-width smaller straight edge strategy strongly universal structure subsection subtrees Theorem upper bounds verify VLSI VLSI layout X-trees