Algebraic Elements of Graphs

About the Book

This book studies algebraic representations of graphs in order to investigate combinatorial structures via local symmetries. Topological, combinatorial and algebraic classifications are distinguished by invariants of polynomial type and algorithms are designed to determine all such classifications with complexity analysis. Being a summary of the author‘s original work on graph embeddings, this book is an essential reference for researchers in graph theory.

Contents
Abstract Graphs
Abstract Maps
Duality
Orientability
Orientable Maps
Nonorientable Maps
Isomorphisms of Maps
Asymmetrization
Asymmetrized Petal Bundles
Asymmetrized Maps
Maps within Symmetry
Genus Polynomials
Census with Partitions
Equations with Partitions
Upper Maps of a Graph
Genera of a Graph
Isogemial Graphs
Surface Embeddability

About the Author :

Yanpei Liu, Beijing Jiaotong University, Beijing, China

Review :
Table of Content:
Preface
Chapter 1 Abstract Graphs
1.1 Graphs and Networks
1.2 Surfaces
1.3 Embeddings
1.4 Abstract Representation
1.5 Notes
Chapter 2 Abstract Maps
2.1 Ground Sets
2.2 Basic Permutations
2.3 Conjugate Axiom
2.4 Transitive Axiom
2.5 Included Angles
2.6 Notes
Chapter 3 Duality
3.1 Dual Maps
3.2 Deletion of an Edge
3.3 Addition of an Edge
3.4 Basic Transformation
3.5 Notes
Chapter 4 Orientability
4.1 Orientation
4.2 Basic Equivalence
4.3 Euler Characteristic
4.4 Pattern Examples
4.5 Notes
Chapter 5 Orientable Maps
5.1 Butterflies
5.2 Simplified Butterflies
5.3 Reduced Rules
5.4 Orientable Principles
5.5 Orientable Genus
5.6 Notes
Chapter 6 Nonorientable Maps
6.1 Barflies
6.2 Simplified Barflies
6.3 Nonorientable Rules
6.4 Nonorientable Principles
6.5 Nonorientable Genus
6.6 Notes
Chapter 7 Isomorphisms of Maps
7.1 Commutativity
7.2 Isomorphism Theorem
7.3 Recognition
7.4 Justification
7.5 Pattern Examples
7.6 Notes
Chapter 8 Asymmetrization
8.1 Automorphisms
8.2 Upper Bounds of Group Order
8.3 Determination of the Group
8.4 Rootings
8.5 Notes
Chapter 9 Asymmetrized Petal Bundles
9.1 Orientable Petal Bundles
9.2 Planar Pedal Bundles
9.3 Nonorientable Pedal Bundles
9.4 The Number of Pedal Bundles
9.5 Notes
Chapter 10 Asymmetrized Maps
10.1 Orientable Equation
10.2 Planar Rooted Maps
10.3 Nonorientable Equation
10.4 Gross Equation
10.5 The Number of Rooted Maps
10.6 Notes
Chapter 11 Maps Within Symmetry
11.1 Symmetric Relation
11.2 An Application
11.3 Symmetric Principle
11.4 General Examples
11.5 Notes
Chapter 12 Genus Polynomials
12.1 Associate Surfaces
12.2 Layer Division of a Surface
12.3 Handle Polynomials
12.4 Crosscap Polynomials
12.5 Notes
Chapter 13 Census with Partitions
13.1 Planted Trees
13.2 Hamiltonian Cubic Maps
13.3 Halin Maps
13.4 Biboundary Inner Rooted Maps
13.5 General Maps
13.6 Pan-Flowers
13.7 Notes
Chapter 14 Equations with Partitions
14.1 The Meson Functional
14.2 General Maps on the Sphere
14.3 Nonseparable Maps on the Sphere
14.4 Maps Without Cut-Edge on Surfaces
14.5 Eulerian Maps on the Sphere
14.6 Eulerian Maps on Surfaces
14.7 Notes
Chapter 15 Upper Maps of a Graph
15.1 Semi-Automorphisms on a Graph
15.2 Automorphisms on a Graph
15.3 Relationships
15.4 Upper Maps with Symmetry
15.5 Via Asymmetrized Upper Maps
15.6 Notes
Chapter 16 Genera of Graphs
16.1 A Recursion Theorem
16.2 Maximum Genus
16.3 Minimum Genus
16.4 Average Genus
16.5 Thickness
16.6 Interlacedness
16.7 Notes
Chapter 17 Isogemial Graphs
17.1 Basic Concepts
17.2 Two Operations
17.3 Isogemial Theorem
17.4 Nonisomorphic Isogemial Graphs
17.5 Notes
Chapter 18 Surface Embeddability
18.1 Via Tree-Travels
18.2 Via Homology
18.3 Via Joint Trees
18.4 Via Configurations
18.5 Notes
Appendix 1 Concepts of Polyhedra, Surfaces, Embeddings and Maps
Appendix 2 Table of Genus Polynomials for Embeddings and Maps of Small Size
Appendix 3 Atlas of Rooted and Unrooted Maps for Small Graphs
Bibliography