Questions tagged [planar-graphs]
A planar graph is a graph (in the combinatorial sense) that can be embedded in a plane such that the edges only intersect at vertices. Consider tagging with [tag:combinatorics] and [tag:graph-theory]. For embeddings into higher-genus spaces, use [tag:graph-embeddings].
1,086
questions
0
votes
1
answer
51
views
Number of squares in a planar Graph [closed]
I need help with the following Graph Theory problem:
Let $G$ be a connected and planar Graph. Each area in the planar version of the Graph (including the outer area) is either a square or a hexagon. ...
0
votes
0
answers
18
views
Combinatorial isomorphisms of 2-connected plane graphs are topological
In Diestel Theorem 4.3.1 (ii) it says "Every combinatorial isomorphism between two 2-connected plane graphs is topological."
I don't understand, where in the proof do we use the fact that ...
- 107
0
votes
1
answer
106
views
Does 'Homeomorphism' describe Kuratowski's theorem accurately?
Let $G=(V,E)$ be a graph.
The edge subdivision operation for an edge $\{u, v\} \in E$ is the deletion of $\{u, v\}$ from $G$ and the addition of two edges $\{u, w\}$ and $\{w, v\}$ along with the new ...
- 2,474
1
vote
0
answers
42
views
Can we take gradient of a curve?
Consider the case of planar curves in $\mathbb{R}^2$. They can be described by a function $f(x,y) = 0$. For example, a circle can be described by $x^2+y^2=1$. We can take the gradient of this function
...
- 101
0
votes
0
answers
65
views
The final step of proving Kuratowski’s Theorem
Recently when I read the proof of the Kuratowski’s Theorem, I was stuck at the final step where it States 4 cases (Since this proof uses many lemmas, it is difficult to give one context related with ...
- 416
2
votes
0
answers
54
views
Positive boolean satisfiability problem : finding minimal solutions.
Consider, over a finite set of boolean variables X, a Boolean system in CNF (conjunctive normal form) whose clauses only contain non-negated literals.
For every assignment of the variables which ...
2
votes
1
answer
106
views
Proof that the maximum number of edges of a 1-planar graph is 4n - 8
The Wikipedia article about 1-planar graphs says that the maximum number of edges in such graphs is $4n - 8$
Every 1-planar graph with n vertices has at most 4n − 8 edges.[4] More strongly, each 1-...
- 155
0
votes
1
answer
42
views
The interior of polygon with n sides and decomposed 7 triangles, 4 squares was found to be a planar representation of a graph with 11 ver. Determine n
The interior of a polygon with n sides and decomposed into 7 triangles and 4 squares was found to be a planar representation of a graph with 11 vertices. Determine n
I tried drawing various figures ...
- 5
0
votes
0
answers
33
views
planar 4 regular graph
if a planar 4 regular graph is only made of 3 and 4 corners and let´s say it has "s" a defined number of 4 corners then how van i find the number of 3 corners using the euler.P.formula . I ...
- 11
0
votes
1
answer
108
views
Planar graphs and isomorphism
If I have a planar graph G and another graph H that's been created by crossing two edges of graph – and its very obviously non-planar. Can I use it as an argument to show that they can not be ...
- 397
0
votes
0
answers
51
views
All simple planar graphs have a vertex of degree at most $5$ (wheel of $n>5$).
Lemma 7.13 All simple planar graphs have a vertex of degree at most 5.
I just read this lemma... wont this lemma fail on wheel of n>5 or am I missing something?
Wheel Graphs: https://en.wikipedia....
0
votes
0
answers
42
views
Why can we assume a triangulated graph without loss of generality, for proofs of the 4 colour theorem?
In the Wikipedia article about the four colour theorem it is stated
First, if planar regions separated by the graph are not triangulated, i.e. do not have exactly three edges in their boundaries, we ...
- 1,125
2
votes
1
answer
44
views
Prove that the complement of a simple embedded graph $G$ is not embeddable on an orientable surface of genus $g$
Problem: Let $G$ be a simple graph embedded on an orientable surface of genus $g$ with $n$ vertices. For which values of $n$ (depending on $g$ ) can we prove that the complement of $G$ is not ...
- 1,238
0
votes
2
answers
135
views
Where does my short proof of the 4-colour theorem go amiss?
The proof is essentially a generalisation of the $5$-Colour Theorem:
Proof. Consider the set $S$ of planar graphs which are not $4$-colourable. Choose the graph $G \in S$ that has the least number of ...
- 392
0
votes
1
answer
43
views
Find the maximum number of edges in a planar subgraph of G
Kuratowski's theorem states that a graph G is non-planar if and only if G has either $K_5$ or $K_{3,3}$ as a minor.
Clearly this graph contains two $K_5$ minors, so our maximum non planar subgraph ...
- 115