Algebraic Elements of Graphs

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