Graphs are widely used abstractions to model systems and interactions, e.g., in molecular chemistry , biochemistry , systems biology  , neuroscience , and social sciences . Therefore, graph theoretical problems play a pivotal role across all disciplines of sciences. However, the combinatorical complexity of graph theoretical problems often hampers practical applications. Despite trees, planar graphs are a graph class for which most optimization or decision problems can efficiently be solved or closely be approximated. This is notably the case for the graph isomorphism problem , graph-coloring problems  and detection of Hamilton cycles , i.e., solving the traveling salesman problem . These facts are reflected in Whitney’s theorem  that proves planar embeddings of 3-connected graphs to be unique up to isomorphism. However, planarity is a very strong condition on the graph G, which often does not match to instances occurring in practice. Extending considerations to graphs of higher genus allow to relax the conditions on the graph structure, which, by itself, is generated by the cycles the graph G contains. However, as counting all elementary cycles is already a #P-hard  problem finding an embedding of minimum genus is NP-hard . In addition, the number of possible embeddings increases exponentially with the graph genus , which in contrast to Whitney’s Theorem makes it hard to efficiently represent G independently of its automorphism class.
Here, we address the question of whether efficiently computable invariants of graphs exist and how they can be used to measure the structural complexity of graphs independently of their representation. Biggs Theorem  is a classic result in graph theory that, similarly to the Euler characteristic of surfaces , provides such an invariant for simple digraphs.
Theorem (Biggs Theorem). The set of connected cycles of a simple digraph G generates a free R-module or vector space of dimension
where #G denotes the connected components of G.
However, Biggs Theorem is only known to hold for the space generated by connected cycles of a simple digraph. Here we generalize the statement to the case of the directed cycle space , spanned by all directed cycles of a multi-digraph G.
1.1. Statement of Contribution
We denote by the set of all directed or connected elementary cycles (passing no vertex twice) of a multi-digraph G and by the induced subgraphs, respectively. Then we prove the following generalization of Biggs Theorem.
Theorem 1 (Biggs Theorem for directed cycles).Let be a multi-digraph and its connected cycle space with respect to . Then
if and only if . (2)
Consequently, in case of equivalence, there holds
Indeed the construction of the induced subgraph is given by the union of all strongly connected components, which therefore can be realized in . Consequently, Theorem 1 allows to determine efficiently in . The efficient computation of potentially addresses many challenging problems in graph theory. In this article, we extend the 1-dimensional CW-complex given by the geometrical realization of G given by attaching 2-cells accordingly to a chosen set of elementary cycles . Thereby, much more structural information of G is understood as topological structure. Theorem 1 enables us to derive formulas for the Betti numbers of the associated homology groups , .
Theorem 2 (Homology of the Elementary Filling). Let be a multi-digraph, , and the geometrical realization induced by the choice of . The associated cellular homology groups are free R-modules of ranks , .
i) and can be computed in .
ii) and .
If then can be computed in .
iii) . If then it is #P-hard (sharp P-hard) to compute .
Using that cellular and singular homology are isomorphic  (Theorem 2.35), Theorem 2 provides a path for computing the singular homology of the geometric realization of G with respect to the set of cycles . To overcome the involvement of a #P-hard counting problem in iii), we suggest several representation independent sub-fillings allowing to compute , , efficiently. Consequently, the graph structure of G can be understood in terms of singular homology. In light of this fact, we revisit classic problems in graph theory as graph embeddings, discrete Morse theory and graph clustering from this new perspective.
For rendering the introduced concepts of this article and the proof Theorem 1 consistent we introduce a definition of graphs that yields a notion of multi-digraphs without requiring multi-sets.
Definition 1. Let be a 4-tuple, where are finite sets and are some maps. We call the elements vertices and the elements edges of G, while are called head and tail of the edge e. An edge e with is called a loop. In general, we call G a multi-digraph. The following cases are often relevant:
i) G is called a digraph iff the map , with is injective.
ii) If there are no loops, i.e., with , then G is called simple.
ii) G is called an undirected graph if G is a digraph and for every there is with , . In this case, we slightly simplify notation by shortly writing e for the pair , which is then called an edge. The notion of can thereby be replaced by with .
iv) In the special case, where the maps are assumed to be canonically given by the relation of E, i.e., , for all .
One readily observes that our definition coincides with the common understanding of graphs. As said, the notion allows to consider multiple edges with , by distinguishing . Thus, no considerations of multi-sets E as in  are needed. We denote with , and #G the number of edges, vertices and the number of connected components of G, respectively.
Two edges e and f are called consecutive if and are called connected if . The degree of a vertex is given by the number of all edges that are connected with v. A directed path of length from a vertex u to a vertex v is a list of consecutive edges , such that and . Thereby, repetition is allowed, i.e., , is possible. A connected path from a vertex u to a vertex v is a list of possible multiple occurring connected edges that become a directed path by exchanging a subset , , of edges with their converse directed versions.
A directed (connected) cycle is a directed (connected) path p from some vertex to itself, which can also be a loop. A cycle is elementary if every vertex it contains is passed exactly once. A cycle is called simple if each edge it contains occurs exactly once. We denote by the set of all connected or directed cycles and with the set of all directed, connected elementary cycles, respectively. In fact, every simple or even non-simple cycle is generated by passing through several elementary cycles , .
Given , we introduce the equivalence relation iff d can be derived from by cyclic reordering, i.e., there is with , . We denote with and the quotients of non-equivalent cycles and count up to equivalence, i.e., , . While non-elementary cycles can coincide in their edge sets but differ in their orderings an elementary cycle is uniquely determined up to cyclic reordering of its edges. This makes elementary cycles the pivotal choice of our considerations. We will slightly abuse notation by making no difference between and , respectively.
Example 1. For G in Figure 1 the cycle is a directed, simple and non-elementary cycle, while the directed cycles and are elementary. Certainly, is given by passing through and . Further, the cycle while . The only reorderings of keeping the edges consecutive are cyclic reorderings.
Figure 1. Elementary and simple cycles.
With , we denote the graphs obtained by deleting the edge e or the vertex v and all its connected edges. Further, , , denote the graph, the set of all edges, and the set of all vertices induced by a set of graphs, edges and vertices. By we denote the power set of a given set A of finite cardinality .
In Section 2, we provide all ingredients to generalize Bigss Theorem and give the proof in Section 3. In Section 4, the 2-dimensional elementary CW complex of G and its homology is studied. Section 5 considers representation invariant sub-fillings while Sections 6 and 7 suggest applications and yield a conclusion of our results.
2. The Module of Cycles
To provide an algebraic notion of cycles we define the characteristic vector representing how often and in which direction an edge is passed by a cycle or path.
Definition 2 (Characteristic Vector). Let be a multi-digraph we introduce the free R-modules,
Let , , be an ordered list of connected edges. Then for we define
If is a cycle then we set if are consecutive and else. If then we set . By considering , the vectors
are called the characteristic vectors of with respect to -and -coefficients.
Remark 1. We want the following fact to be clear. The characteristic vector depends on the ordering of . However, if are connected elementary cycles such that are equivalent. Then holds. If are directed then even holds. Thus, the maps
are well defined.
Definition 3 (Incidence operator). Let be a multi-digraph. We denote with , the -linear incidence operator operators, defined on the generators by
By choosing an enumeration , we can represent by the classic incidence matrix with
The notion of is given by setting .
By Remark 1 the characteristic vector , might depend on the ordering of c. However, the kernel of is not sensitive to the possible choices of signs. Therefore, we obtain a well defined algebraic notion of cycles as follows.
Lemma 3. Let be a multi-digraph and be a set of elementary cycles. Then we denote with
the set of all characteristic vectors induced by cycles in O. The free generated cycle modules are given by
where , denotes the span with respect to .
Proof. The identities follow directly by the definition of . Further, we verify that for any list of connected edges, due to (6), we have
proving the claim.
To characterize the cycle spaces we rephrase Biggs Theorem  for connected cycles of simple digraphs matching our setup and notation.
Theorem 4 (Biggs Theorem). Let be a simple digraph then the dimension of the connected cycle spaces are given by
where #G denotes the number of connected components of G.
Indeed, for simple digraphs the first line of the incidence matrix in (11) is unnecessary and thereby our definition yields the classic notion of for any fixed enumeration of . In fact, the proof of Theorem 4 is based on computing the rank of , which is independent of the chosen enumeration, yielding our reformulation to be genuine. Due to Lemma 3 we obtain the following consequence.
Corollary 1 (Biggs Theorem for connected cycles of multi-digraphs). Let be a multi-digraph. Then the dimension of the connected cycle spaces are given by
where #G denotes the number of connected components of G.
Proof. Indeed, each loop or multiple edge increases the dimension by 1. More precisely: Every loop or two cycle , is R-linear independent, to all other elements in . Thus, by removing e we obtain . Recursively applying this procedure ends up with a simple digraph with . Thus, due to Theorem 4 we compute
How to generalize the characterisation of cycle spaces in the directed case is provided in the next section.
3. Biggs Theorem for Directed Cycles
We prove a generalization, we introduce the concept of contracting edges in a multi-digraph as follows.
Definition 4 (Contracted Graph). Let be a multi-digraph and . Let , . An equivalence relation on V is defined by
The equivalence class of is denoted by and gives the quotient of V with respect to . Further, we define and set
The multi-digraph is called the contracted graph of G with respect to . If then we observe that . Thus, if is a subgraph then can be defined by contracting in arbitrary order, yielding a well defined notion.
Remark 2. Let be a simple digraph and such that are consecutive and . Then becomes a multi-digraph, i.e., h and f become parallel edges in . Furthermore, the contraction of a two cycle , , results in a loop . These phenomena are the reasons why we consider multi-digraphs with loops, rendering the notion of contracted graphs consistent within our framework. Certainly, contraction preserves connectivity, i.e., .
Now we have all ingredients to state the first main theorem of this article.
Theorem 5 (Biggs Theorem for directed cycles). Let be a multi-digraph and its cycle space with respect to . Then
if and only if . (21)
Consequently, in case of equivalence, there holds
Proof. The proof splits into several steps:
Step 1: We show . Indeed, given . Then we can generate by characteristic vectors of directed elementary cycles , . Thus, every hast to be contained in at least one of them proving .
Step 2: We show . Indeed, implies that by Lemma 3 is a free sub-module of . Thus, it suffices to show (22) in order to prove the converse inclusion. We argue by induction on . If then there are only loops. Thus,
and the claim follows. Now assume that . Let be not a loop; then we consider the contracted graph . Let if and or , then certainly . If then remains elementary. If and then consists of two elementary cycles with one of them being a loop. Thus, . By induction, we therefore compute
Step 2a: We show that . Let with . By choosing an equivalent cycle , if necessary w.l.o.g. we can assume that c is ordered such that , , . Conversely, for every cycle we choose an ordering such that either or becomes a cycle in . We consider the map
Given , such that are a basis of . Then induces a -linear injective lift
Step 2b: We show that . Indeed, if is such that has no negative entries then and . If this is not the case then the entry corresponding to f is the only negative entry. Since there is with .
For any we denote by the directed subpath of connecting x and y. Further, let be all crossing vertices such that for the edges with we have and , . Analogously, we consider all crossing vertices such that for the edges with we have and . Moreover, we assume that and that the are ordered w.r.t the ordering of directed path . We consider two cases.
Case 1: If then setting , yields , see Figure 2 and thereby
Case 2: If then we construct three cycles by
see again Figure 3 for an illustration, where is indicated by the black lines. Since are elementary we have that the connected components of
Figure 2. Sketch of the cycle construction for Case 1.
are pairwisely disjoint paths. Moreover, are elementary. Therefore, we verify again that
holds and thereby implies that . Hence, and we have proven Step 2. Thus, due to Corollary 1 we have proven the theorem for .
Step 3: For the claim follows by using that is equivalent to as proven above. Then the identity
proves the theorem with respect to -coefficients.
Remark 3. For simplification, the sketch of Case 2 in Figure 3 assumes that the paths are not nested, which might be not true in general. However, this circumstance does not affect (29) nor the fact that are elementary, which were all assumptions we used for the argumentation.
An immediate consequence of Theorem 5 is the following.
Corollary 2. Let be a multi-digraph. Then
can be determined in .
Proof. By Theorem 5 we have and therefore . Now is given by the union of all strongly connected components of G which can be computed in linear time  yielding the claim due to (22).
The opportunity of computing the dimension of the directed cycles space efficiently, potentially addresses many challenging problems in graph theory. We use the result to study the structure of G in terms of cellular homology groups.
4. The CW Complex of Elementary Cycles
An excellent introduction to algebraic topology is given by Allen Hatcher .
Figure 3. Sketch of the cycle construction for Case 2.
Especially, the notion of CW complexes, geometric realizations and the classic theory of simplicial and cellular homology were presented explicitly therein. The following notions and results take these concepts for granted.
Definition 5 (Coherent Orientation). Let be a multi-digraph and be a set of elementary connected cycles. A map is called a coherent orientation w.r.t. O iff
i) for all
ii) for all characteristic vectors with .
Lemma 6. Let be a multi-digraph and be a set of elementary connected cycles. Then there exists a coherent orientation .
Proof. We argue by induction on . If then we choose an ordering and thereby a representative of all equivalent cycles in O. Thus, setting with defines a coherent orientation. Now assume that . Let and be the set of all cycles being not equivalent to c. We consider and a splitting into elementary connected components. That is
By induction there is a coherent orientation w.r.t. . Let be the characteristic vector of c. Assume there are with and . Then belong to different components, i.e., , , . Observe, that we can change to on every component by keeping the requirements of a coherent orientation preserved. Thus, we can change to such that for all . Hence, setting on and for all yields a coherent orientation.
Definition 6 (Elementary CW Complex). Let be a multi-digraph and be its geometric realization. Further, let be a set of elementary connected cycles. The geometric realization given by attaching 2-cells to accordingly to O is called the elementary CW complex of G w.r.t. O. Further, shall denote the set of -cells of , and
the maps yielding the identification of -cells with vertices, edges and cycles, respectively.
Indeed, for the complexes , the cellular homology can be derived by considering the following chain complexes.
Definition 7 (Elementary Chain Complex). Let G be a multi-digraph, , be a set of elementary connected cycles, and be a coherent orientation w.r.t. O. Let be the associated CW complex. We consider the free generated R-modules
For , we define the boundary operators , on the generators by ,
For we consider and , respectively. We enforce to be R-linear by setting , for all , , , . Finally, we set and for .
Remark 1 asserts why even in case of -coefficients the maps yield well defined boundary operators. More precisely:
Theorem 7. Let be a multi-digraph, be a set of connected elementary cycles and be a coherent orientation w.r.t. O. Let be the elementary CW complex, and be given due to Definition 7.
i) The pairs define a finite chain complex, i.e., for all .
ii) The cellular homology groups are free R-modules ,
iii) The Betti numbers are given by
Proof. By considering the sequence
the identities , follow for . For and we consider the induced characteristic vectors
Then we observe that , , where denotes the incidence operator of G. Thus, if and only if corresponds to a cycle, i.e., , . By definition of and Lemma 3, this yields and consequently , showing (i). Furthermore, we realize that, and . Thus, is free generated by O, implying that . By using the dimension formula we realize that the quotient is a free R-module of dimension
Likewise, implies that . Since and are free R-modules, there are isomorphisms , . Let ↪ be the natural embedding and be a basis of then can be extended to a basis of and yields a basis of containing as a sub-basis of . Thus,
showing that the 1-st homology is a free R-module of dimension
Since and are free R-modules we analogously observe that there is a sub-basis of generating . Hence, is a free R-module of dimension
which proves (iii).
Remark 4. Note that the Betti numbers do not depend on the choice of the coherent orientation o. Even though, Lemma 6 provides the existence of a coherent orientation o an explicit construction of o, which might be computational expensive, is not necessary to compute the , .
Remark 5. The singular homology of any CW complex X is isomorphic to its cellular homology  (Theorem 2.35). Thus, Theorem 7 provides a path for computing the singular homology of the elementary CW complexes . Further, we obtain the following consequence that yields main Theorem 2.
Corollary 3. Let the assumptions of Theorem 7 be fulfilled and denote with the R-rank of the cellular homology group , .
i) can be computed in .
ii) and can be computed in .
iii) Computing , is #P-hard (sharp P-hard).
Proof. The number of connected components of any multi-graph can be determined by breadth-first search within , yielding i) due to Theorem 7. To show ii), recall that by Lemma 3, we have that yielding . Due to Corollary 2, computing can be done in . Thus, by Theorem 7, the bottleneck for computing is again given by determing #G yielding ii). Now iii) is a consequence of Theorem 7 and the fact that, by reduction to the Hamiltonian cycle problem, counting the number of all directed (connected) elementary cycles of a digraph is #P-hard .
We recall that two multi-digraphs and are called homeomorphic if there are sets of directed paths such that for any inner vertex of or , respectively, and the graphs given by contracting are isomorphic.
Corollary 4. Let and be two homeomorphic multi-digraphs. We denote with , , consider the elementary CW complexes , , and . Then
Proof. As one can readily verify, neither the number of cycles , nor the dimension , nor the number of connected components of change under the contraction of the paths , yielding the claim due to Theorem 7.
Due to Corollary 3 (3) counting is #P-hard. Though there are efficient algorithms  counting the number of cycles approximately, we, here, suggest to consider certain sub-fillings to yield an suitable setup.
5. Representation Invariant Sub-Fillings
In this section we discuss several possibilities of filling the graph G by choosing , such that the cellular homology of the resulting CW complexes can be computed efficiently and the filling is invariant under automorphisms, i.e., is independent of the chosen representation of G. The list below is by no means complete and just provides some suggestions.
5.1. Fillings Induced by Cycle Bases
If the cycles are R-linear independent then due to Theorem 7 for the CW complex the Betti numbers are given by , and . Thus, is given by the co-dimension of in . Thereby, fillings by R-linear independent cycles or basis yield only trivial topological information.
5.2. Fillings Induced by Shortest Cycles
Let be a multi-digraph. We consider the set of all shortest cycles
Further, , , denote the set of all incoming or outgoing edges of , and their unions.
Lemma 8. Let be a multi-digraph and its maximum degree.
ii) can be determined in .
Proof. Note that the all-shortest path problem, which is to find a shortest connected path between all pairs of vertices is very well studied. In the case of integer edge weights, as we consider here, for instance the algorithms of  , solve the problem in much less then . We consider all edges with shortest path of minimum length such that becomes a shortest cycle . For any outgoing edge we denote with and with the possibly empty shortest cycle w.r.t. . Then we observe that
Thus, i) follows. Further, due to Edsger W. Dijkstra’s famous shortest path algorithm  each cycle can be computed in yielding ii).
Certainly, for all isomorphic graphs . Further, the associated Betti numbers , , of can be computed efficiently due to Lemma 8 and Theorem 7. Indeed the bottleneck is given by computing , which requires at most by applying Gauss elimination or can be done even faster .
Recursively applying this procedure to the contraction provides an array of Betti numbers , , that decodes the structure of G independently of the chosen representation. We expect that this efficiently provided information is quite informative for structural analysis. That is: multi-digraphs with for all are similar and are not isomorphic whenever differ for some .
5.3. Fillings Induced by Cliques
Let , , denote the complete undirected graph of n vertices, . Then the number of cycles , up to cyclic reordering, is given by all subsets of vertices larger than 3, i.e.,
which can be computed in . Since , computing the Betti numbers of can be done in . Let be the set of all cliques of size . Let , with . Then we consider a set of cycles such that and , . The geometric realization is a canonical filling in the following sense:
The number of cycles can be computed efficiently due to (54). On the other hand contains all triangles of , which generate , . Thus, . Hence, due to Theorem 7 the associated Betti numbers can be computed efficiently once the cliques have been determined.
Note that the general clique problem, i.e., finding a clique of given size in a graph G, belongs to the list of classic NP-complete problems . However, if the size n is fixed, finding cliques can be done efficiently in . Even better performs the Bron-Kerbosch algorithm, which lists all maximal cliques . Many other contributions in regard of clique detecting algorithms were made, allowing us to find a non-trivial filling as described above efficiently. Consequently, the homology groups yield a method of decoding how the cliques are glued with each other.
We expect the concept of studying a graph G by computing its cellular homology groups with respect to specified fillings to open up many possible applications. A short, non-exclusive list of ideas is presented below.
6.1. Graph Embeddings
We strengthen the classic notion of cellular graph embeddings as follows.
Figure 4. Embeddings of into (left) and (right).
Definition 8 (Elementary embedding). Let G be a simple undirected graph, its 1-dimensional geometric realization, and S a compact, connected -surface without boundary. Given a continuous embedding
we set and let be the CW complex given by attaching the set of disjoint 2-cells in the canonical way. We say that is an elementary embedding of G into S if and only if there is a CW-complex embedding
Thus, there are no edge crossings in , and every 2-cell in corresponds to some 2-cell in . By considering digraphs and replacing with directed notions can be derived.
Remark 6. Note that the usual notion of 2-cell embeddings of graphs is given by requiring only that
is an embedding, such that is given by the union of 2-cells. Hence, an elementary embedding of G into S is a special case of a cellular embedding and therefore a stronger requirement on the embedding . The following example makes this circumstance visible.
Example 2. Figure 4 illustrates embeddings of into the projective plane and the torus . We recall that can be understood as the quotient of a disc with the equivalence relation ~ defined on the boundary by identifying opposite points , . In contrast, the torus is given by identifying opposite sides of a square. Consequently, the embedding of into is an elementary embedding, while the boundary of in is not an elementary cycle. Therefore, the embedding of into is a 2-cell embedding, but not an elementary embedding.
Remark 7. Note furthermore, that in contrast to cellular embeddings an elementary embedding needs not to exist. For instance consider 2 cubes intersecting
in only one vertex. An elementary embedding could only be realized by allowing S to consist of two spheres intersecting in one point, requiring a relaxation that allows S to be a polyfold.
Given a simple undirected graph G with such that there is a surface S and an elementary embedding ↪ . Observe that the Euler characteristic of S is given by
Since S is a closed surface, we have , while when S is orientable and if S is non-orientable .
Thus, if then S is given by the unit sphere or the projective plane and G is required to be (projective) planar. The detection and construction of a (projective) planar cell embedding can be done in  . In general, the problem of finding a cellular embedding of G into a orientable surface S of minimal genus is NP-complete . However, finding a cellular embedding into a surface S of maximal genus is polynomial time solvable . Our strengthened notion of embeddings and the relaxation of S being allowed to be non-orientable might provides new insights into embedding theory. Note that S is determined if we can find such that:
i) For every there are exactly 2 cycles with .
Thus, due to this simple description, one might finds new methods as integer linear programming techniques (ILP), which construct O and thereby S. By changing (2) into the case of polyfold embeddings is treated, see Remark 7.
6.2. Graph Clustering
Many applications require comparing graphs or clustering a set of graphs into subsets of “similar” graphs. The distance functions used to measure similarity between graphs often lead to NP-complete optimization problems and can only be approximated. For instance, the graph-edit distance  is a (pseudo) metric measuring the cost of deleting and inserting the minimum number of edges and vertices required to modify a graph into a graph . Determining this distance in general is an NP-hard problem, which is why additional assumptions and restrictions to special graph classes are usually made. We posit that any feasible clustering of a given set of graphs , i.e., , , and , must fulfill the following properties:
a) Let be isomorphic or more generally homeomorphic, then belong to the same cluster, i.e., for some .
b) Given , the problem of deciding whether and will belong to the same cluster is solvable in polynomial time.
b) The similarity distance is a (pseudo) metric.
As a consequence of (c) we have that if , for all and some , then for all , . We propose that the following distance definition based on our work leads to a feasible clustering:
Definition 9. Let be a given set of multi-digraphs and be sets of elementary cycles of , . Then, we define the homological distance by
Certainly, is a pseudo metric. Further, due to Section 5, we can choose fillings that ensure that the Betti numbers, and thereby , can be computed efficiently. We denote with and let , be the variance of the . Consider a maximum set of graphs , with for all , then
yields a clustering that satisfies (a), (b), and (c) above. Due to the fact that the Betti numbers measure the topological complexity of the graphs, we expect that such a clustering will be informative in structural data analysis.
6.3. Discrete Morse Theory
Let X be a CW complex, K the set of cells of X, and a given function. If the (discrete) gradient flow of f possesses no degenerate critical points or singularities f is called a discrete Morse function . In this regard, the strong and weak Morse inequalities become important, stating that
where denotes the number of critical cells of a Morse function f with Morse index n, and are the Betti numbers of X w.r.t. some field e.g. . Thus, if is given by a filling of G then we can bound the essential complexity of the dynamics from below. Since the Betti numbers do not depend on the Morse function, we can furthermore determine whether there are homotopies that reduce the complexity of the system without loosing any of its essential dynamics .
We extended the classic Theorem of Biggs to the case of directed cycles of multi-digraphs. These findigs were then incorporated to extend the classic interpretation of a graph G being a 1-dimensional CW complex to the 2-dimensional case by attaching 2-cells accordingly to an a priori specified set of elementary cycles . We proved the associated cellular homology groups , to be free R-modules and derived formulas for computing their Betti numbers. Of course, one could ask for extending these considerations to even higher dimensions. However, in order to describe a 3-cell, we need to know all cycles forming its boundary. Thus, dealing with higher-dimensional cells makes computing the Betti numbers combinatorically harder, which made us restricting to the presented case.
7.1. Classic Graph-Theoretical Problems
It is natural to ask the question how classic graph-theoretical problems behave for certain classes of graphs. Here we provided some methods to classify graphs with respect to certain aspects of their topology. The fillings presented in Section 5 might be a good starting point of investigating classic graph theoretical problems on graphs with bounded topological complexity in terms of the derived Betti numbers. For instance the Feedback Arc Set Problem, which is to delete as less edges as possible to make G acyclic, could profit from certain obstructions on the cycle topology,  , as derived in Section 5.2. Further, the understanding of cliques of a graph is crucial if one wants to determine its chromatic numbers . Despite for coloring problems , the minimal genus of a graph plays an important role within the unresolved Graph Isomorphism Problem  or extensions of Whitney’s Theorem .
7.2. Related Complexes and Homology Theories
In addition to the concepts presented here, there are multiple other possibilities of assigning complexes and (co)-homologies to a given graph G   . Translations of these theories in terms of our contribution are certainly of interest.
 Dokholyan, N.V., Li, L., Ding, F. and Shakhnovich, E.I. (2002) Topological Determinants of Protein Folding. Proceedings of the National Academy of Sciences, 99, 8637-8641.
 Otte, E. and Rousseau, R. (2002) Social Network Analysis: A Powerful Strategy, Also for the Information Sciences. Journal of Information Science, 28, 441-453.
 Hopcroft, J.E. and Wong, J.K. (1974) Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report). In: Proceedings of the 6th Annual ACM Symposium on Theory of Computing, STOC ‘74, ACM, New York, 172-184.
 Deı, V.G., Klinz, B., Woeginger, G.J., et al. (2006) Exact Algorithms for the Hamiltonian Cycle Problem in Planar Graphs. Operations Research Letters, 34, 269-274.
 Karp, R.M. (1972) Reducibility among Combinatorial Problems. In: Miller, R.E. and Thatcher, J.W., Eds., Complexity of Computer Computations, Plenum Press, New York, 85-103.
 Babai, L. (2016) Graph Isomorphism in Quasi-Polynomial Time. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, ACM, New York, 684-697.