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
94
votes
1
answer
3k
views
Number of simple edge-disjoint paths needed to cover a planar graph
Let $G=(V,E)$ be a graph with $|E|=m$ of a graph class $\mathcal{G}$. A path-cover $\mathcal{P}=\{P_1,\ldots,P_k\}$ is a partition of $E$ into edge-disjoint simple paths. The size of the cover is $\...
- 3,768
42
votes
6
answers
22k
views
Four color theorem disproof?
My brother in law and I were discussing the four color theorem; neither of us are huge math geeks, but we both like a challenge, and tonight we were discussing the four color theorem and if there were ...
- 651
37
votes
1
answer
4k
views
Euler's formula doesn't work for null graph?
Given the null graph with no edges or vertices, we have a connected planar graph as no edges cross when this graph is drawn in the plane, and the fact that any two distinct vertices have a path ...
- 3,019
26
votes
3
answers
7k
views
Is this graph a planar graph or not?
I've been trying to find out if this graph is planar or not for a while and have really been coming up short when it comes to creating a planar drawing of the graph. My intuition is telling me that it'...
- 719
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
18
votes
0
answers
382
views
Algorithms for "pleasing" drawings of planar graphs, possibly on sphere
What algorithms exist to draw planar graphs without edge crossings in a way that they are easy to interpret by humans?
There are multiple algorithms that can handle any planar graph, such as Schnyder'...
- 1,127
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
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
10
answers
3k
views
Can you explain to me why this proof by induction is not flawed? (Domain is graph theory, but that is secondary)
Background
I am following this MIT OCW course on mathematics for computer science.
In one of the recitations they come to the below result:
Official solution
Task:
A planar graph is a graph that can ...
- 294
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
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
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
14
votes
1
answer
625
views
5-color coloring game.
Let there be two players, $A$ and $B$, and a map.
They now play a game such that:
Player $A$ picks a region and player $B$ colors it such that the region is a different color than all adjacent ...
- 796
12
votes
1
answer
2k
views
Why is this proof for the four color theorem considered wrong?
I'd like to think I found a proof for the four color theorem, but I also know that it took far smarter people than me a computer simulation to prove. Still, I don't see why this logic should be flawed....
- 247
12
votes
3
answers
7k
views
Algorithm for planarity test in graphs
I am implementing a graph library and I want to include some basic graph algorithms in it. I have read about planar graphs and I decided to include in my library a function that checks if a graph is ...
