Yanpei Liu

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

This two-volume set presents combinatorial functional equations using an algebraic approach, and illustrates their applications in combinatorial maps, graphs, networks, etc. The second volume mainly presents several kinds of meson functional equations which are divided into three types: outer, inner and surface. It is suited for a wide readership, including pure and applied mathematicians, and also computer scientists.

This two-volume set presents combinatorial functional equations using an algebraic approach, and illustrates their applications in combinatorial maps, graphs, networks, etc. The first volume mainly presents basic concepts and the theoretical background. Differential (ordinary and partial) equations and relevant topics are discussed in detail.

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

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