Crossing Numbers of Graphs (Discrete Mathematics and Its Applications)

Description

Crossing Numbers of Graphs is the first book devoted to the crossing number, an increasingly popular object of study with surprising connections. The field has matured into a large body of work, which includes identifiable core results and techniques. The book presents a wide variety of ideas and techniques in topological graph theory, discrete geometry, and computer science. The first part of the text deals with traditional crossing number, crossing number values, crossing lemma, related parameters, computational complexity, and algorithms. The second part includes the rich history of alternative crossing numbers, the rectilinear crossing number, the pair crossing number, and the independent odd crossing number.It also includes applications of the crossing number outside topological graph theory. Aimed at graduate students and professionals in both mathematics and computer science The first book of its kind devoted to the topic Authored by a noted authority in crossing numbers 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