All Questions
Tagged with planar-graphs general-topology
23
questions
2
votes
1
answer
42
views
Genus of a graph consisting of two faces homeomorphic to open disks
Suppose the graph $G$ is embedded in a surface $Q$ such that there are two faces $F_1,F_2$ of the embedding, each homeomorphic to the open disk, such that each node of $G$ lies on $F_1$ or $F_2$.
Is ...
- 468
0
votes
0
answers
76
views
Proving the 4-color theorem. [duplicate]
I have a question as to why the four color theorem has not been proved by hand.
I believe that to prove the four color theorem, it suffices to show that a complete graph may only be planar if it has 4 ...
- 1
1
vote
1
answer
86
views
Breaking chocolate problem and Euler characteristic.
There is the following Problem:
Given an $m \times n$ chocolate bar, where you can only break it along the gridlines and only break one piece at the time. What is the minimum amout of steps needed to ...
- 870
1
vote
0
answers
422
views
Showing genus of a Petersen graph is equal to 1
In relation to the question asked here Genus of Petersen graph could a possible solution be to construct a rectangle which represents an embedding on a torus where the opposite edges are identified (...
- 87
1
vote
1
answer
71
views
A question regarding Graph embedding in plane
I am new to Algebraic Topology. So, I would like to have a detailed proof of this following problem as there are many similar and corollary problems in the book that I am reading.
Suppose we are given ...
- 13
2
votes
0
answers
126
views
Mac Lane's Planarity Criterion Proof
Given a graph $G$, we denote $\mathcal{C}(G)$ its cycle space. We say that a basis $B$ of $\mathcal{C}(G)$ is a $2$-basis if every element of $B$ is a cycle and every edge of $G$ belongs to at most ...
- 456
5
votes
0
answers
200
views
Alexander duality and simplicial complexes
A consequence of Alexander duality is the fact that an $n$-dimensional simplicial complex $K$ embedded in $\mathbb{R}^{n+1}$ separates $\mathbb{R}^{n+1}$ into $\beta_n + 1$ connected components where $...
- 732
1
vote
1
answer
80
views
Links of a 2-complex embedded in $\mathbb{R}^3$
Let $K$ be a 2-dimensional simplicial complex embedded in $\mathbb{R}^3$. The link of a vertex $v$ in $K$ is the graph $\text{Lk}(v)$ whose vertices are the edges incident to $v$ in $K$. Two vertices ...
- 732
5
votes
1
answer
1k
views
The relationship between the Euler characteristic and the fundamental group of finite connected graphs
I have been asked to conjecture a relationship between the Euler characteristic and the fundamental group of finite connected graphs and, if possible, to prove the conjecture.
We know that if the ...
- 2,907
3
votes
1
answer
2k
views
Why can the complete graph K5 be embedded on a torus?
In the Question Which complete graphs can be embedded on a torus? the poster says, that the complete graph $K_5$ can be embedded on a torus.
But the Euler characteristic of the torus is 0 and the ...
- 169
9
votes
2
answers
775
views
Infinite graph is planar iff it can be embedded in sphere
My question is about the following statement about planar graphs:
A graph is planar (i.e. can be embedded in the plane) if and only if it can be embedded in the sphere $S^2$.
By an embedding we ...
- 171
6
votes
1
answer
162
views
Condition that the faces of a graph be unique?
There is a theorem that if a planar graph is 3-vertex-connected, then it has a unique embedding up to a reflection. (See e.g. here.) This means that its faces and its dual graph are uniquely defined.
...
- 1,127
0
votes
1
answer
139
views
These two trees are not equivalent
Two trees $T_{1}$ and $T_{2}$ in the plane are equivalent if there exists a homeomorphism $f$ of the plane such that $f(T_{1})=T_{2}$. Suppose we are given the following two trees in the picture
I ...
- 560
2
votes
0
answers
93
views
Natural extensions of Fary's Theorem?
When recently reading about the remarkable (but somewhat intuitive) Fary's Theorem, I wondered about natural extensions of it to other spaces, none of which were listed on the Wikipedia page.
It's ...
- 3,285
4
votes
1
answer
815
views
Embedding of a Graph in a Sphere
Let $G$ be a finite connected graph and $f:G\to S^2$ be an embedding of $G$ into $S^2$ (we are assuming that $G$ can be embedded in $S^2$). Think of the graph as a $1$-dimensional CW complex.
Is it ...
- 18.7k