Crossing Numbers of Graphs

Cover
Half Title
Title Page
Copyright Page
Dedication
Table of Contents
Preface
List of Figures
List of Tables
Symbol Description
I: The Crossing Number
	1: The Conjectures of Zarankiewicz and Hill
		1.1 Drawings with Crossings
			1.1.1 A Puzzle
			1.1.2 Distinguishing Drawings of Graphs
			1.1.3 The Crossing Lemma
			1.1.4 The Parity Lemma
		1.2 Zarankiewicz and the Crossing Number of Complete Bipartite Graphs
			1.2.1 Exact Values
			1.2.2 Minimal Drawings
			1.2.3 Asymptotic Behavior
		1.3 Hill and the Crossing Number of Complete Graphs
			1.3.1 Exact Values
			1.3.2 Asymptotic Behavior
			1.3.3 Random Drawings
		1.4 Notes
		1.5 Exercises
	2: Drawings and Values
		2.1 Good Drawings of Complete Graphs
			2.1.1 Basic Properties
			2.1.2 Enumeration
			2.1.3 Extremal Properties
		2.2 Crossing Numbers of Graphs
			2.2.1 Cartesian Products of Graphs
			2.2.2 Cycles and the Harary-Kainen-Schwenk Conjecture
				2.2.2.1 The Hypercube
			2.2.3 More Complete Graphs
			2.2.4 Crossing-Critical Graphs
		2.3 Notes
		2.4 Exercises
	3: The Crossing Number and Other Parameters
		3.1 Bisection Width and Graph Layout
		3.2 Embeddings and Congestion
		3.3 Measures of Planarity
			3.3.1 Skewness
			3.3.2 Edge Crossing Number
			3.3.3 Thickness
		3.4 Chromatic Number and Albertson's Conjecture
		3.5 Beyond the Plane
			3.5.1 Genus
			3.5.2 Crossings on Surfaces
			3.5.3 Crossing Sequences
			3.5.4 Minors
		3.6 Notes
		3.7 Exercises
	4: Complexity and Algorithms
		4.1 The Hardness of Crossing Number Problems
		4.2 Drawing Graphs with Rotation
			4.2.1 How to Draw K2,n
			4.2.2 The Cyclic-Order Graphs
		4.3 Good Drawings of the Complete Graph
			4.3.1 Testing Goodness
			4.3.2 Gioan's Theorem
		4.4 Computing the Crossing Number
		4.5 Notes
		4.6 Exercises
II: Crossing Number Variants
	5: The Rectilinear Crossing Number: Rectilinear and Pseudolinear Drawings
		5.1 A First Look
		5.2 Pseudolines and the Pseudolinear Crossing Number
			5.2.1 Pseudolines and Wiring Diagrams
			5.2.2 Pseudolinear and Good Drawings
			5.2.3 Structure in Pseudolinear Drawings
			5.2.4 The Pseudolinear Crossing Number
			5.2.5 Stretchability and Complexity
			5.2.6 The Complexity of the Rectilinear Crossing Number
		5.3 Rectilinear Drawings
			5.3.1 Enumeration of Rectilinear Drawings
			5.3.2 Structure in Rectilinear Drawings
		5.4 Notes
		5.5 Exercises
	6: The Rectilinear Crossing Number: Values and Bounds
		6.1 A Look at the Complete Graph
			6.1.1 Sylvester's Four Point Problem
			6.1.2 Upper Bounds
			6.1.3 Lower Bounds and k-Edges
			6.1.4 Pseudolinear Drawings and Bishellability
		6.2 Other Graphs
		6.3 Notes
		6.4 Exercises
	7: The Local Crossing Number
		7.1 Local Crossings
			7.1.1 Simple, or Not?
			7.1.2 Density of Graphs with Few Local Crossings
			7.1.3 Local Crossings on Surfaces
		7.2 1-planarity
			7.2.1 A Map Coloring Problem
			7.2.2 Complexity of 1-Planarity Testing
		7.3 Rectilinear Drawings
			7.3.1 Rectilinear 1-planarity
			7.3.2 Rectilinear Local Crossing Number
		7.4 Quasi-k-planarity
		7.5 Notes
		7.6 Exercises
	8: Book and Monotone Crossing Numbers
		8.1 Embeddings and Drawings in Books
			8.1.1 Book Embeddings and Their Thickness
			8.1.2 A Single Page
				8.1.2.1 One-Page Drawings
				8.1.2.2 The Convex Crossing Number
			8.1.3 Two Pages
			8.1.4 The Book Crossing Number
		8.2 Monotonicity
			8.2.1 Monotone Drawings
			8.2.2 The Monotone Crossing Number
		8.3 Notes
		8.4 Exercises
	9: The Pair Crossing Number
		9.1 Counting Pairs
		9.2 A Crossing Lemma
		9.3 String Graphs
			9.3.1 A Separator Theorem
			9.3.2 Improving the pcr-Bound
		9.4 Notes
		9.5 Exercises
	10: The k-planar Crossing Number
		10.1 Drawing in k Planes
		10.2 Bounds and Values
			10.2.1 Complete Bipartite Graphs
			10.2.2 Complete Graphs
			10.2.3 Random Graphs
		10.3 Rectilinear and Geometric k-Planar Crossing Numbers
		10.4 Notes
		10.5 Exercises
	11: The Independent Odd Crossing Number
		11.1 Removing Even Crossings
		11.2 The Independent Odd Crossing Number
			11.2.1 An Algebraic Invariance of Good Drawings
			11.2.2 The Strong Hanani-Tutte Theorem
			11.2.3 A Crossing Lemma
		11.3 Lower Bounds on Odd Crossings
		11.4 Algebraic Crossing Numbers
		11.5 Separations
			11.5.1 Translating Separations
			11.5.2 Algebraic Crossings Matter
			11.5.3 Odd Crossings Matter
			11.5.4 Adjacent Crossings Matter
		11.6 Disjoint Edges in Topological Graphs
		11.7 Notes
		11.8 Exercises
	12: Maximum Crossing Numbers
		12.1 Polygons and Cycles
		12.2 Complete Graphs
		12.3 Thrackles
			12.3.1 The Thrackle Bound
			12.3.2 Conway's Thrackle Conjecture
			12.3.3 Generalized Thrackles
			12.3.4 Superthrackles
			12.3.5 A Better Bound
			12.3.6 Geometric and Monotone Thrackles
			12.3.7 The Subthrackle Bound
		12.4 The Subgraph Monotonicity Problem
		12.5 Hypercubes
		12.6 Complexity
		12.7 Notes
		12.8 Exercises
III: Appendices
	A: Basics of Topological Graph Theory
		Appendix A
			A.1 Curves
			A.2 Embeddings and Planar Graphs
			A.3 Bigons
			A.4 Graphs on Surfaces
			A.5 Rotations and Embedding Schemes
			A.6 Crossings in Drawings
			A.7 Notes
			A.8 Exercises
	B: Basics of Complexity
		Appendix B
			B.1 Algorithms, Time, and Space
			B.2 Computational Complexity
			B.3 Notes
			B.4 Exercises
Bibliography
Index