Topological Theory of Graphs

ISBN-13: 9783110476699 / Angielski / Twarda / 2017 / 369 str.

Yanpei Liu;University of Science & Technology

Opis

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

Recenzje

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

O autorze

Yanpei Liu, Beijing Jiaotong University, Beijing, China.