Let $x,y,z\in\mathbb{R}$ vertices and the “wrap” $g\in\mathrm{G}$ an edge. Then wie have the vertices head and tail and the edges prev and next.

component(e)
mark(e);
e' := e;
while(e'≠ e) do
e' := next(e');
if (e' == e) return true;
mark(e');
endwhile
e':=e;
while (e' ≠ NULL) do
e' := prev(e');
if(e'==e) return false;
mark(e');
endwhile

findcomponents()
num_circles :=0;
num_ints :=0;
unmark all edges;
for each edge e do
if (marked(e)) continue;
if (component(e))
then num_circles ++;
else num_ints++;
endif

Data Structure for surfaces

There are winged edges, half edges and quad edges. An oriented edge has the vertices head and tail and the faces left and right.

head-next(e) = – r-next(e)
head-prev(e) = – l-next(e)
tail-next(e) = – l-prev(e)
tail-prev(e) = – r-prev(e)

There is a duality: vertex $\leftrightarrow$ face, edge $\leftrightarrow$ edge ($\bot$) and face $\leftrightarrow$ vertex.
Quad edge represents both together, vertex and face are the same data structure (e.g. coordinates of vertex area of dual face). A “quad edge<2 has pointers to four vertices/faces and pointers to four other quad edges.
Store quad edge once. A reference to a quad edge is a pointer to this data structure together with two bits $±e$, $±e^+$. We need enumerators for each edge, vertex and face. and some pointers back from a vertex/face to an incident edge.

mark all edges, faces, vertices
for each edge e do
if unmarked(e)
then find_component(left(e));
end for


find_component(f)
recursively mark all neighbors (breath-first or order-first, pruning when we see a marked face);
As we go, count faces, edges, vertices;

If we pass a marked face again with oposite direction, set a “nonorientability” flag.

Need to count components: $\chi = \mathrm{V}-\mathrm{E}+\mathrm{F}$.
With some modifications quad edges, etc. also work for multigraphs in a surface.

Similarly, for any 2-complex in $\mathbb{R}^3$ or for a 3-manifold given as a 3-complex we can use facet edge data structure.
A facet edge $f_e$ represents one edge of one face in the complex.

next_edge($f_e$), next_facet($f_e$), prev_edge($f_e$), prev_edge($f_e$)

The facet edge has four pointers to $f_e$’s, 2 pointer to vertices (head, tail) and 2 pointers to cells (above, below).
Especially when the complex forms a closed 3-manifold, we can implement duality as quad edge.

Topic: polygons, polyhedra, cell complexes and data structure for these.

$n$-manifolds looks locally like $\mathbb{E}$. Further a $n$-manifold with boundary has points with neighboorhoods like a halfspace $\{x\in \mathbb{E}^n | x_n\geq 0\}$. Compact manifolds (with boundary) are the ones that can be represented in the computer, say by a finite triangulation.

Definition: A closed $n$-manifold is a compact manifold without boundary.

Each component of a $0$-manifold is a point. The manifold is compact iff it is finite. A connected $1$-manifold is $\bigcirc\cong\mathbb{S}^1, \:\mid\:\cong [0,1],\:\updownarrow \:\cong\mathbb{R}\cong(0,1)$ or $\uparrow \:\cong\mathbb{R}_{\geq 0} \cong [0,1)$. Thus, a compact $1$-manifold has finitely many components, each is $\mathbb{S}$ or $\mathrm{I}$.
Recall: each component of a compact $2$-manifold is $\sum_{g,k}$ if orientable or $\mathrm{N}_{h,k}$ if not.
Represent a compact $1$-manifold by gluing edges together: Start with n edges and some identifications of the end points (an equivalence relation on the set of $2n$ end points). In general this gluing gives a multigraph with $n$ edges and less than $2n$ vertices. The size of each equivalence class is the degree of the resulting vertex. A finite multigraph can be realized this way iff there is no vertex of degree $0$.

Lemma: A multigraph is a $1$-manifold iff every vertex has degree $1$ or $2$.

Definition: The body is exactly the set of all vertices of degree $1$.

For $2$-dimensional manifolds (and cell complexes) we start with a finite collections of polygons and a rule for gluing edges. Equivalently, we can require that all the polygons are triangles.

Definition: An oriented $n$-gon is topologically an oriented closed disk with n marked boundary-points $a_i$ in cyclic order.

The gluing rule is an equivalence relation on the set of all oriented edges with the porperty that $e\sim f \Leftrightarrow -e \sim -f$. The equivalence classes are the oriented edges of the resulting $2$-complex.
The degree or valence of the resulting edfe is the cardinality of the equivalence class. The resulting compact space is a $2$-manifold iff all edges has valence $1$ or $2$ and edges of valence $1$ form the boundary. We get a manifold if we start with pairing of the oriented edges. The manifold is closed (no boundary) if all edges get paired.

The $2$-complex we get is always purely $2$-dimensional (no edges of valence $0$, no isolated vertices). Not every purely $2$-dimensional complex can be obtained by our construction. We’ve given a “top-down” $\:$construction of complexes. Start with to-dimensional cells gluing their face.
The other construction of cell complexes is “bottom up”.$\:$Start with a finite set of vertices. Then sew in a finite collection of edges (to head and tail vertices). Finally sew in $n$-gons by attaching boundary to a cycle of $n$ oriented edges.
With this second construction edge valence is $0$ or $2$ is necessary but not sufficient to get a manifold with boundary. We need to test that the link of each vertex is connected. Assuming the valence conditions, the link of each vertex is a $1$-manifold – we just need to check if it is $\mathrm{I}$ or $\mathbb{S}^1$.
Usually we have geometric information about how a complex is sitting in some ambient space. E.g. each vertex has coordinates. Usually edges are straight lines in the ambient space.
We may need to mark edges to say which “way around”$\:$ in the ambient space they go. If the ambient space is $\mathbb{R}^3/\:\mathrm{G}$ for some crystallographic group $\mathrm{G}$, then we often represent vertices as points $v\in\mathbb{R}^3$. An edge from $v$ to $w$ is marked with $g\in\mathrm{G}$ to show that it is the straight line $v$, $g\cdot w$ is one of the preimages.
Sometimes multiple edges are usefull even if the start in the same position.