User:DVD206/Graphs and manifolds

The main subjects of study of this book are the graphs, embedded in surfaces (2D manifolds), their local and global properties, and connections between them.

A graph G = {V, E} is a pair of sets, where E\in\P(V) is a subset of the power set P(V). We will refer to the elements of V as vertices, and elements of E as edges or hyper-edges.

A 2D manifold is a topological space, such that around every point p of the manifold there is an open set U homeomorphic to the unit disc D, and the homeomorphisms are coherent.

${\begin{cases}\phi _{(}p)=0,\\\phi _{U}(U)=\mathbf {D} \end{cases}}$

We will say that a graph G is embedded in a manifold M, if vertices ~ points, curves ~edges... In topological graph theory, an embedding (also spelled imbedding) of a graph $G$ on a surface Σ is a representation of $G$ on Σ in which points of Σ are associated to vertices and simple arcs (homeomorphic images of [0,1]) are associated to edges in such a way that:

• the endpoints of the arc associated to an edge $e$ are the points associated to the end vertices of $e$,
• no arcs include points associated with other vertices,
• two arcs never intersect at a point which is interior to either of the arcs.

A directed graph with boundary is a triple G = (V,\partial V,E}, where V is a set of points in a space, called vertices, \partial V is the subset of V called boundary vertices, and E is a set of directed pairs of elements of V, called edges.

For every edge (a,b) in E we call b a neighbor of a.