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].
138
questions
18
votes
1
answer
34k
views
How to prove that a simple graph having 11 or more vertices or its complement is not planar?
It is an exercise on a book again. If a simple graph $G$ has 11 or more vertices,then either G or its complement $\overline { G } $ is not planar.
How to begin with this? Induction?
Thanks for your ...
- 357
14
votes
2
answers
13k
views
A space curve is planar if and only if its torsion is everywhere 0
Can someone please explain this proof to me. I know that a circle is planar and has nonzero constant curvature, so this must be an exception, but I am a little lost on the proof.
Thanks!
- 575
15
votes
3
answers
48k
views
Every planar graph has a vertex of degree at most 5.
I am trying to prove the following statement, any help!?
Prove that every planar graph has a vertex of degree at most 5.
- 169
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
7
votes
4
answers
32k
views
Understanding proof for $e \leq 3v - 6$ in planar graphs
I have a proof for a property of a planar graph:
Lemma 5.8.4. In a planar embedding of a connected graph, each edge is traversed once by each of two different faces, or is traversed exactly twice by ...
- 2,493
5
votes
2
answers
887
views
every planar graph can be expressed as a union of five edge-disjoint forests
How can I prove that every planar graph can be expressed as a union of (maximum) five edge-disjoint forests?
Only thing I can think about is going somehow like the $5$ color theorem but I get stuck ...
- 186
4
votes
1
answer
656
views
Generating the $n^{th}$ full binary tree over $N$ labeled leaves
I am looking for an algorithm to incrementally generate distinct full binary trees over $N$ unique leaves. That is, I want an algorithm that can generate the $n^{th}$ distinct tree without generating ...
- 165
2
votes
1
answer
5k
views
Prove that a bipartite planar graph has a vertex of degree at most 3
Exam preparation.
I'm a bit confused on where to start with this question. How could one approach this question?
- 279
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
14
votes
3
answers
3k
views
Can there exist an uncountable planar graph?
I'm currently revising a course on graph theory that I took earlier this year.
While thinking about planar graphs, I noticed that a finite planar graph corresponds to a (finite) polygonisation of the ...
- 839
11
votes
1
answer
14k
views
Euler's formula for triangle mesh
Can anyone explain to me these two facts which I don't get from Euler's formula for triangle meshes?
First, Euler's formula reads $V - E + F = 2(1-g)$ where $V$ is vertices number, $E$ edges number, $...
- 767
6
votes
3
answers
12k
views
Prove that $K_{3,3}$ is not planar.
Prove that $K_{3,3}$ is not planar.
This problem comes from A Course in Combinatorics (Problem 1D). At this point, the authors have introduced merely the most basic concepts of graphs, so this is ...
- 8,656
3
votes
2
answers
5k
views
3-regular connected planar graph
Let $G$ be a 3-regular connected planar graph with a planar embedding where each face has degree either 4 or 6 and each vertex is incident with exactly one face of degree 4. Determine the number of ...
- 147
2
votes
3
answers
2k
views
Multipartite graphs which are not planar
Please take a look at these definitions:
A multipartite graph is a graph of the form $K_{r_1,\ldots, r_n}$ where
$n > 1$, $r_1, \ldots, r_n\ge 1$, such that
The set of nodes of the ...
- 111
2
votes
1
answer
2k
views
Prove: If $G$ is a planar graph with $p$ vertices, $q$ edges, and finite girth $g$ then, $q \leq \frac{g(p−2)}{g−2}$ .
Prove the following theorem:
If $G$ is a planar graph with $p$ vertices, $q$ edges, and finite girth $g$ then, $$q \leq \frac{g(p−2)}{g−2}$$ .
I do not know how to go about proving this, besides the ...
- 37