Topological Theory of Graphs

by Yanpei Liu, University of Science & Technology (Contribution by)

Overview

This book presents a topological approach to combinatorial configurations, in particular graphs, by introducing a new pair of homology and cohomology via polyhedra. On this basis, a number of problems are solved using a new approach, such as the embeddability of a graph on a surface (orientable and nonorientable) with given genus, the Gauss crossing conjecture, the graphicness and cographicness of a matroid, and so forth. Notably, the specific case of embeddability on a surface of genus zero leads to a number of corollaries, including the theorems of Lefschetz (on double coverings), of MacLane (on cycle bases), and of Whitney (on duality) for planarity. Relevant problems include the Jordan axiom in polyhedral forms, efficient methods for extremality and for recognizing a variety of embeddings (including rectilinear layouts in VLSI), and pan-polynomials, including those of Jones, Kauffman (on knots), and Tutte (on graphs), among others.

Contents

Preliminaries

Polyhedra

Surfaces

Homology on Polyhedra

Polyhedra on the Sphere

Automorphisms of a Polyhedron

Gauss Crossing Sequences

Cohomology on Graphs

Embeddability on Surfaces

Embeddings on Sphere

Orthogonality on Surfaces

Net Embeddings

Extremality on Surfaces

Matroidal Graphicness

Knot Polynomials

Product Details

ISBN-13:	9783110476699
Publisher:	De Gruyter
Publication date:	03/06/2017
Pages:	369
Product dimensions:	6.69(w) x 9.45(h) x (d)
Age Range:	18 Years

About the Author

Yanpei Liu, Beijing Jiaotong University, Beijing, China.

Table of Contents

1 Preliminaries 1

1.1 Sets and relations 1

1.2 Partitions and permutations 5

1.3 Graphs and networks 9

1.4 Groups and spaces 15

1.5 Notes 20

2 Polyhedra 22

2.1 Polygon double covers 22

2.2 Supports and skeletons 25

2.3 Orientable polyhedra 28

2.4 Non-orientable polyhedra 30

2.5 Classic polyhedra 32

2.6 Notes 34

3 Surfaces 35

3.1 Polyhegons 35

3.2 Surface closed curve axiom 39

3.3 Topological transformations 42

3.4 Complete invariants 46

3.5 Graphs on surfaces 48

3.6 Up-embeddability 52

3.7 Notes 56

4 Homology on Polyhedra 58

4.1 Double cover by travels 58

4.2 Homology 60

4.3 Cohomology 65

4.4 Bicycles 70

4.5 Notes 75

5 Polyhedra on the Sphere 78

5.1 Planar polyhedra 78

5.2 Jordan closed-curve axiom 84

5.3 Uniqueness 87

5.4 Straight-line representations 91

5.5 Convex representation 93

5.6 Notes 95

6 Automorphisms of a Polyhedron 97

6.1 Automorphisms of polyhedra 97

6.2 Eulerian and non-Eulerian codes 102

6.3 Determination of automorphisms 110

6.4 Asymmetrization 124

6.5 Notes 127

7 Gauss Crossing Sequences 129

7.1 Crossing polyhegons 129

7.2 Dehn's transformation 133

7.3 Algebraic principles 137

7.4 Gauss crossing problem 141

7.5 Notes 143

8 Cohomology on Graphs 145

8.1 Immersions 145

8.2 Realization of planarity 148

8.3 Reductions 151

8.4 Planarity auxiliary graphs 154

8.5 Basic conclusions 158

8.6 Notes 163

9 Embeddability on Surfaces 165

9.1 Joint tree model 165

9.2 Associate polybegons 167

9.3 A transformation 168

9.4 Criteria of embeddability 171

9.5 Notes 173

10 Embeddings on Sphere 175

10.1 Left and right determinations 175

10.2 Forbidden configurations 179

10.3 Basic order characterization 185

10.4 Number of planar embeddings 192

10.5 Notes 197

11 Orthogonality on Surfaces 198

11.1 Definitions 198

11.2 On surfaces of genus zero 205

11.3 Surface models 225

11.4 On surfaces of genus not zero 228

11.5 Notes 229

12 Net Embeddings 231

12.1 Definitions 231

12.2 Face admissibility 236

12.3 General criterion 242

12.4 Special criteria 248

12.5 Notes 255

13 Extremality on Surfaces 257

13.1 Maximal genus 257

13.2 Minimal genus 261

13.3 Shortest embedding 264

13.4 Thickness 273

13.5 Crossing number 275

13.6 Minimal bend 277

13.7 Minimal area 283

13.8 Notes 288

14 Matroidal Graphicness 291

14.1 Definitions 291

14.2 Binary matroids 292

14.3 Regularity 295

14.4 Graphicness 300

14.5 Cographicness 305

14.6 Notes 306

15 Knot Polynomials 308

15.1 Definitions 308

15.2 Knot diagram 312

15.3 Tutte polynomial 317

15.4 Pan-polynomial 320

15.5 Jones Polynomial 327

15.6 Notes 329

Bibliography 331

Subject Index 347

Author Index 355

Editorial Reviews

Table of Content:
Preface
Chapter 1 Preliminaries
1.1 Sets and relations
1.2 Partitions and permutations
1.3 Graphs and networks
1.4 Groups and spaces
1.5 Notes
Chapter 2 Polyhedra
2.1 Polygon double covers
2.2 Supports and skeletons
2.3 Orientable polyhedra
2.4 Nonorientable polyhedral
2.5 Classic polyhedral
2.6 Notes
Chapter 3 Surfaces
3.1 Polyhegons
3.2 Surface closed curve axiom
3.3 Topological transformations
3.4 Complete invariants
3.5 Graphs on surfaces
3.6 Up-embeddability
3.7 Notes
Chapter 4 Homology on Polyhedra
4.1 Double cover by travels
4.2 Homology
4.3 Cohomology
4.4 Bicycles
4.5 Notes
Chapter 5 Polyhedra on the Sphere
5.1 Planar polyhedra
5.2 Jordan closed curve axiom
5.3 Uniqueness
5.4 Straight line representations
5.5 Convex representation
5.6 Notes
Chapter 6 Automorphisms of a Polyhedron
6.1 Automorphisms
6.2 V -codes and F-codes
6.3 Determination of automorphisms
6.4 Asymmetrization
6.5 Notes
Chapter 7 Gauss Crossing Sequences
7.1 Crossing polyhegons
7.2 Dehns transformation
7.3 Algebraic principles
7.4 Gauss Crossing problem
7.5 Notes
Chapter 8 Cohomology on Graphs
8.1 Immersions
8.2 Realization of planarity
8.3 Reductions
8.4 Planarity auxiliary graphs
8.5 Basic conclusions
8.6 Notes
Chapter 9 Embeddability on Surfaces
9.1 Joint tree model
9.2 Associate polyhegons
9.3 A transformation
9.4 Criteria of embeddability
9.5 Notes
Chapter 10 Embeddings on the Sphere
10.1 Left and right determinations
10.2 Forbidden Congurations
10.3 Basic order characterization
10.4 Number of planar embeddings
10.5 Notes
Chapter 11 Orthogonality on Surfaces
11.1 Denitions
11.2 On surfaces of genus zero
11.3 Surface Model
11.4 On surfaces of genus not zero
11.5 Notes
Chapter 12 Net Embeddings
12.1 Denitions
12.2 Face admissibility
12.3 General criterion
12.4 Special criteria
12.5 Notes
Chapter 13 Extremality on Surfaces
13.1 Maximal genus
13.2 Minimal genus
13.3 Shortest embedding
13.4 Thickness
13.5 Crossing number
13.6 Minimal bend
13.7 Minimal area
13.8 Notes
Chapter 14 Matroidal Graphicness
14.1 Denitions
14.2 Binary matroids
14.3 Regularity
14.4 Graphicness
14.5 Cographicness
14.6 Notes
Chapter 15 Knot Polynomials
15.1 Denitions
15.2 Knot diagram
15.3 Tutte polynomial
15.4 Pan-polynomial
15.5 Jones polynomial
15.6 Notes
Reference
Index

From the Publisher