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
6
votes
4
answers
3k
views
planar regular bipartite graph
(a) Prove that there exists a 3-regular planar bipartite graph $G$ with $4n$ vertices for all $ n\geq 3$.
(b) Prove that does not exist a 3-regular planar bipartite graph with $10$ vertices.
The ...
- 3,853
7
votes
2
answers
5k
views
Degree of vertices in planar graph
Here is the problem:
Let $G$ a planar graph with $12$ vertices. Prove that there exist at
least $6$ vertices with degree $\leq 7$.
Here it is what I did:
Since $G$ is planar the number of its ...
- 3,853
14
votes
2
answers
2k
views
"Planar" graphs on Möbius strips
Is there an easy way to tell if a graph can be embedded on a Möbius strip (with no edges crossing)?
A specific version of this: if a simple graph with an odd number of vertices has all vertices of ...
- 55.9k
16
votes
4
answers
80k
views
Checking whether a graph is planar
I have to check whether a graph is planar. The given type is
$$ e ≤ 3v − 6 .$$
From Wikipedia:
Note that these theorems provide necessary conditions for planarity that are not sufficient ...
- 1,081
2
votes
1
answer
789
views
Planar graph embedding algorithm
I'm looking for a planar graph embedding algorithm description. Actually, it would be nice if I knew at least names of these algorithms. The only one I know is called γ(gamma)-algorithm, and it has an ...
- 417
4
votes
4
answers
7k
views
What is a rigorous way to prove that this graph is non-planar?
What is a rigorous way to prove this graph is non-planar? I have some vague memories of setting the edges within the boundary of the graph as vertices and then use some adjacency rule to check to see ...
- 3,117