Graph theory: Embedding and genus

In summary, the question at hand is if a graph of genus g can be embedded on a surface of genus g, are the resulting faces 2-cells? While there is an intuitive belief that this is true, a more mathematical argument or proof is being sought. It is noted that if a 3-cycle (genus 0) is embedded on a Torus (genus 1), the faces may not be 2-cells if the cycle goes around the handle of the Torus, but if it is embedded in a different way, the faces are indeed 2-cells. This serves as a hint that the answer is yes, but a rigorous argument is desired. References to any relevant papers or sources would be appreciated
  • #1
math8
160
0
Let [itex]G[/itex] be a graph of genus [itex]g[/itex].

Let [itex]S_g[/itex] be a surface of genus [itex]g[/itex] (equivalent to the Torus with [itex]g[/itex] handles).

The question is: If we embed [itex]G[/itex] on [itex]S_g[/itex], are the faces that we obtain 2-cells (homeomorphic to disks)?

I believe the answer is yes (intuitively). But, is there an argument that is more mathematic to express this? If there is some sort of page or paper that talks about this, that would be very helpful.

Note: I can see that if we try to embed a 3-cycle( genus 0) on a Torus(genus 1 [itex]\neq 0[/itex] ), in a way that the cycle goes 'around' the handle of the Torus, then the faces are not 2-cells.
 
Physics news on Phys.org
  • #2
But, if we embed the 3-cycle on the Torus in a way that it does not go around the handle of the Torus, then the faces are 2-cells. So, this gives me a hint that this is true. But, I am looking for some sort of rigorous proof/argument. Thanks!
 

What is graph theory?

Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures used to model and analyze relationships between objects.

What is embedding in graph theory?

Embedding in graph theory refers to the process of representing a graph in a geometric space, such as a plane or a surface, while preserving its structure and properties.

What is genus in graph theory?

Genus in graph theory is a measure of the complexity of a graph, defined as the minimum number of cuts needed to transform the graph into a planar graph (a graph that can be embedded in a plane without any edges crossing).

Why is embedding and genus important in graph theory?

Embedding and genus are important in graph theory because they allow us to study and analyze the properties of graphs in a more visual and intuitive way. They also have applications in various fields, such as computer science, physics, and sociology.

What are some common applications of embedding and genus in graph theory?

Some common applications of embedding and genus in graph theory include network analysis, circuit design, map coloring, and graph algorithms, such as the famous Four Color Theorem.

Similar threads

Replies
2
Views
4K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
988
  • Calculus and Beyond Homework Help
Replies
1
Views
440
  • Calculus and Beyond Homework Help
Replies
11
Views
4K
  • Introductory Physics Homework Help
Replies
1
Views
393
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
22
Views
3K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
Back
Top