A Guide to Graph Algorithms

Contents
Preface
About the authors
Acknowledgments
Graphs
	1.1 Isomorphic Graphs
	1.2 Representing graphs
	1.3 Neighborhoods
	1.4 Connectedness
	1.5 Induced Subgraphs
	1.6 Paths and Cycles
	1.7 Complements
	1.8 Components
		1.8.1 Rem ' s Algorithm
	1.9 Separators
	1.10 Trees
	1.11 Bipartite Graphs
	1.12 Linegraphs
	1.13 Cliques and Independent Sets
	1.14 On Notations
Algorithms
	2.1 Finding and counting small induced subgraphs
	2.2 Bottleneck domination
	2.3 The Bron & Kerbosch Algorithm
		2.3.1 A Timebound for the B & K – Algorithm
	2.4 Total Order!
		2.4.1 Hypergraphs
		2.4.2 Problem Reductions
	2.5 NP – Completeness
		2.5.1 Equivalence covers of splitgraphs
			Chromatic index
	2.6 Lov asz Local Lemma
		2.6.1 Bounds on dominating sets
		2.6.2 The Moser & Tardos algorithm
		2.6.3 Logs and witness trees
		2.6.4 A Galton Watson branching process
	2.7 Szemer edi's Regularity Lemma
		2.7.1 Construction of regular partitions
	2.8 Edge thickness and stickiness
		Computing stickiness
	2.9 Clique Separators
		2.9.1 Feasible Partitions
		2.9.2 Intermezzo
		2.9.3 Another Intermezzo: Trivially perfect graphs
	2.10 Vertex ranking
		2.10.1 Permutation graphs
		2.10.2 Separators in permutation graphs
		2.10.3 Vertex ranking of permutation graphs
	2.11 Cographs
		2.11.1 Switching cographs
	2.12 Parameterized Algorithms
	2.13 The bounded search technique
		2.13.1 Vertex cover
		2.13.2 Edge dominating set
		2.13.3 Feedback vertex set
		2.13.4 Further reading
		References
	2.14 Matchings
	2.15 Independent Set in Claw - Free Graphs
		2.15.1 The Blossom Algorithm
		2.15.2 Minty ' s Algorithm
		2.15.3 A Cute Lemma
		2.15.4 Edmonds ' Graph
	2.16 Dominoes
	2.17 Triangle partition of planar graphs
		The dual
		The triangle partition algorithm
		Graphs without separating triangles
		Graphs with separating triangles
		2.17.1 Intermezzo: PQ – trees
	2.18 Games
		2.18.1 Snake
		2.18.2 Grundy values
		2.18.3 De Bruijn's game
		2.18.4 Poset games
		2.18.5 Coin - turning games
		2.18.6 NIM - multiplication
		2.18.7 P3 - Games
		2.18.8 Chomp
Problem Formulations
	3.1 Graph Algebras
	3.2 Monadic Second – Order Logic
		3.2.1 Sentences and Expressions
		3.2.2 Quanti cation over Subsets of Edges
Recent Trends
	4.1 Triangulations
		4.1.1 Chordal Graphs
		4.1.2 Clique – Trees
	4.2 Treewidth
		Treewidth of Claw – Free Graphs
		4.2.1 Treewidth and brambles
			Further reading
		4.2.2 Tree - decompositions
		4.2.3 Example: Steiner tree
			Partitions of a set
			Steiner trees
			Processing the tree - decomposition
			Process at a start node
			Process at an introduce node
			Process at a forget node
			Process at a join node
			Conclusion
			Must - reads on Steiner trees
		4.2.4 Treewidth of Circle Graphs
			Crossing Separators
			Minimal Separators in Circle Graphs
			An algorithm to compute the treewidth of circle graphs
	4.3 On the treewidth of planar graphs
		4.3.1 Antipodalities
		4.3.2 Tilts and slopes
		4.3.3 Bond carvings
		4.3.4 Carvings and antipodalities
	4.4 Tree - degrees of graphs
		4.4.1 Intermezzo: Interval graphs
	4.5 Modular decomposition
		4.5.1 Modular decomposition tree
		4.5.2 A linear - time modular decomposition
			Refinement
			Promotion
			Assembly
			Conclusion
			Further reading
		4.5.3 Exercise
	4.6 Rankwidth
		4.6.1 Distance hereditary - graphs
		4.6.2 Intermezzo: Perfect graphs
		4.6.3 χ Boundedness
		4.6.4 Governed decompositions
		4.6.5 Forward Ramsey splits
		4.6.6 Factorization of trees
		4.6.7 Kruskalian decompositions
		4.6.8 Exercise
	4.7 Clustered coloring
		4.7.1 Bandwidth and BFS - trees with few leaves
		4.7.2 Connected partitions
		4.7.3 A decomposition of Kt minor free graphs
		4.7.4 Further reading
	4.8 Well Quasi Orders
		4.8.1 Higman's Lemma
		4.8.2 Kruskal's Theorem
		4.8.3 Gap embeddings
	4.9 Threshold graphs and threshold - width
		4.9.1 Threshold width
		4.9.2 On the complexity of threshold - width
		4.9.3 A fixed - parameter algorithm for threshold - width
	4.10 Black and white - coloring
		4.10.1 The complexity of black and white - coloring
	4.11 k – Cographs
		4.11.1 Recognition of k – Cographs
		4.11.2 Recognition of k – Cographs — revisited
		4.11.3 Treewidth of Cographs
	4.12 Minors
		4.12.1 The Graph Minor Theorem
	4.13 General Partition Graphs
	4.14 Tournaments
		4.14.1 Tournament games
		4.14.2 Trees in tournaments
			Well - rooted trees
			Further reading
		4.14.3 Immersions in tournaments
			What happened earlier ..
			Linked layouts
			Gap sequences
			Marches
			Codewords
			Encoding
		4.14.4 Domination in tournaments
	4.15 Immersions
		4.15.1 Intermezzo: Topological minors
			Further reading on topological minors:
		4.15.2 Strong immersions in series - parallel digraphs
		4.15.3 Intermezzo on 2 - trees
		4.15.4 Series parallel - triples
			Parallel compositions
			F - Series parallel trees
			Truncations and portraits
		4.15.5 A well quasi - order for one way series parallel - triples
		4.15.6 Series parallel separations
		4.15.7 Coda
		4.15.8 Exercise
	4.16 Asteroidal sets
		4.16.1 AT - free graphs
		4.16.2 Independent set in AT-free graphs
		4.16.3 Exercise
		4.16.4 Bandwidth of AT-free graphs
		4.16.5 Dominating pairs
		4.16.6 Antimatroids
		4.16.7 Totally balanced matrices
			Further reading
		4.16.8 Triangle graphs
	4.17 Sensitivity
		4.17.1 What happened earlier ...
		4.17.2 Cauchy's interlace lemma
		4.17.3 Hypercubes
			The proof of the hypercube theorem
		4.17.4 Möbius inversion
		4.17.5 The equivalence theorem
		4.17.6 Further reading
	4.18 Homomorphisms
		4.18.1 Retracts
		4.18.2 Retracts in threshold graphs
		4.18.3 Retracts in cographs
	4.19 Products
		4.19.1 Categorical products of cographs
		4.19.2 Tensor capacity
		4.19.3 Cartesian products
			Independence domination
		4.19.4 Independence domination in cographs
		4.19.5  e(Kn x Kn)
			The tensor product Kn x Kn
	4.20 Outerplanar Graphs
		4.20.1 k – Outerplanar Graphs
		4.20.2 Courcelle ' s Theorem
		4.20.3 Approximations for Planar Graphs
		4.20.4 Independent Set in Planar Graphs
	4.21 Graph isomorphism
		Must - reads on graph isomorphism
Bibliography
Index