43
votes
Accepted
A conjecture on planar graphs
Let $L(G)=\sum_{xy\in E(G)} \min\lbrace\deg(x),\deg(y)\rbrace$.
THM. For a simple planar graph with $n$ vertices, $L(G)\le 18n-36$ for $n\ge 3$.
PROOF. Recall that a simple planar graph with $k\ge 3$ ...
- 37.7k
27
votes
Accepted
Is the divisibility graph of the proper divisors of n more often planar than not?
No, because almost all numbers have at least $4$ distinct prime factors, making the divisibility graph contain a hypercube and thus be nonplanar.
- 148k
17
votes
Accepted
Can all crossings in a graph be moved to one point?
No, this is not always possible.
Lemma. Let $G$ be an $n$-vertex graph with at least $3n-2$ edges. Then $G$ cannot be drawn in the plane so that all crossings occur at the same point.
Proof. We make ...
- 32.1k
11
votes
Accepted
Does every $4$-connected nonplanar graph contain a $K_5$-minor?
Yes, this is true and follows from Wagner's theorem. Wagner's theorem asserts that every graph with no $K_5$ minor can be built from $0$-, $1$-, $2$-, and $3$-sums from planar graphs and a fixed $8$ ...
- 32.1k
10
votes
A conjecture on planar graphs
This is just an elaboration on Brendan McKay's beautiful answer, but too long for a comment. The crucial idea is to simplify the problem by generalising it, introducing a maximisation on the indices ...
- 1,169
10
votes
Accepted
Do planar graphs have an acyclic two-coloring?
G. Chartrand, H.V. Kronk, C.E. Wall showed in "The point-arboricity of a graph" (Israel J. Math., 6 (1968), pp. 169–175) that the vertex-set of any planar graph can be partitioned into three induced ...
- 1,169
10
votes
Accepted
Orientations of Planar Graphs
Such an orientation always exists, here is a proof.
Take your 2-edge-connected graph $G$, and consider its dual graph $D$. $D$ has a proper 4-coloring in which each face of $D$ contains at most 3 ...
- 935
10
votes
There is a 3-connected 5-regular simple $n$-vertex planar graph iff $n$ satisfies....?
There are no such graphs when $n$ is odd, by the handshaking lemma.
Conversely, for all even $n \geq 224$, we claim such a graph exists.
In particular, given two planar 5-regular graphs $G$, $H$ each ...
- 12.4k
10
votes
Accepted
There is a 3-connected 5-regular simple $n$-vertex planar graph iff $n$ satisfies....?
There is a 3-connected 5-regular simple $n$-vertex planar graph if and only if $n=12$ or $n \ge 16$ is even. See Recursive generation of 5-regular graphs by Mahdieh Hasheminezhad, Brendan D. McKay, ...
- 4,589
10
votes
Accepted
Generating 21-vertex 4-regular plane graphs with 8 faces of degree 3 and 15 faces of degree 4
Brinkmann and McKay's program plantri can generate planar quadrangulations, which are planar graphs with all faces of size 4.
If you generate these on 23 vertices ...
- 12.7k
9
votes
Threshold function for a graph not being planar
In the Erdős–Rényi model, the threshold for the planarity is know to be $t(n) = 1/n$. Perhaps one of the easiest ways to see this is the following.
If $p=o(1/n)$, then a straightforward union bound ...
- 1,209
9
votes
Accepted
Has Plummer's open problem on the cyclic connectivity of planar graphs been solved?
Yes, it has been solved.
In 1989 Borodin proved that the maximum cyclic edge connectivity of a 5-connected planar graph is at most 11, improving on Plummer's upper bound of 13. The 11 bound is tight [...
- 188k
8
votes
Method to draw 3-connected planar graph on a sphere
If the graph $G=(V,E)$ has a lot of symmetries, then using spectral realizations might give you nice drawings that reflects these symmetries. The success of this method (e.g. whether the drawing is ...
- 13.6k
8
votes
Accepted
In how many ways can a given planar graph be mapped into the plane?
It is a theorem of Whitney, that a $3$-connected planar graph has two planar embeddings (one being the other flipped over). If a graph is two-connected, then you can flip over some, but not all of the ...
- 96.4k
8
votes
Why $K_5$ and $K_{3,3}$?
I have now found a paper by A. Skopenkov where he proves the theorem from the fact that $K_5$ and $K_{3,3}$ are the only graphs $G$ with the property
For each edge $x y$, the Graph $G - x - y$ does ...
- 857
8
votes
Accepted
Distribution over Penrose Tilings?
At stated in the comments, all Penrose tilings contain any finite patch infinitely often, so your criterion doesn't narrow things down much. But judging from the sort of intuitive notion you're ...
- 3,068
8
votes
Threshold function for a graph not being planar
Consider the model where a random graph is made by adding one edge at a time chosen uniformly at random from edges not yet present.
Łuczak, Pittel and Wierman (1994) showed that there is a function $f(...
- 37.7k
7
votes
Accepted
A question regarding the all pair shortest paths in weighted planar graphs
This can be done in quadratic time using the linear-time single-source shortest path algorithm by Henzinger et al.
- 1,250
7
votes
Accepted
How to prove that there does not exist any plane isotopy from the logarithmic spiral onto the real line?
A stronger result is true: there is no homeomorphism of the plane which takes the spiral to the line.
If the spiral is defined exactly as in your question (does not contain the origin) this is evident:...
- 91.8k
7
votes
Accepted
Is there easy proof for triangle-free two-coloring of planar graphs?
Thomassen does indeed prove the vertex version, but in a different paper. In fact this paper proves the stronger statement that you can get a coloring without monochromatic triangles from any 2-list ...
- 85.5k
7
votes
Distribution over Penrose Tilings?
The tiling space of the penrose tilings is uniquely ergodic with respect to the translation action. As is any reasonable notion of the 'canonical transversal' (also sometimes called the discrete hull) ...
- 715
6
votes
Accepted
The origin of a planar graph theorem of Steinitz and Rademacher
According to Frank Lutz's article it's in paragraph 46 of the Steinitz-Rademacher book: "every triangulated 2-sphere can be reduced to the boundary of the tetrahedron by a sequence of edge ...
- 188k
5
votes
Is there easy proof for triangle-free two-coloring of planar graphs?
Yes, there is an extremely short and elegant proof by Carsten Thomassen. See this paper, Prop 2.5.
In fact it is so short that I'll give it in full:
Proof (by induction on $|V(G)|$). If $|V(G)|\le 4$...
- 37.7k
5
votes
When is an ordering of edges in a graph a planar embedding?
The ordering of edges around each vertex allows to find the cycles that bound the faces. In particular, one can compute the number of faces. The given ordering corresponds to a planar embedding if and ...
- 6,337
5
votes
Accepted
Is there a way to generate all 5-connected 5-regular planar graphs?
The answer is yes.
This construction is from the paper "Pairs of Hamiltonian circuits in 5-connected planar graphs" by Joseph Zaks. This is the "connected sum" of a 5-regular ...
- 9,501
5
votes
Accepted
Planar graphs - more or less
These are the graphs with pairwise crossing number or pair-crossing number at most $k$. Note that it is an open problem whether the pair-crossing number is actually equal to the usual crossing number ...
- 32.1k
5
votes
Accepted
Sharp upper bound of the number of edges for graphs of thickness two
There is no such graph on $11$ vertices, but for all $n \geq 12$, there exists a thickness-$2$ graph with $6n-12$ edges. Both these results were proved by Boswell and Simpson in Edge-disjoint maximal ...
- 32.1k
4
votes
Accepted
Does every finite bridgeless cubic planar simple undirected graph admit a 2-factorization with at most two components each of which has even order?
If one takes a planar cubic non-Hamiltonian graph, and takes the vertex connect sum of 3 copies, then it cannot have such a 2-factor. It's not hard to check that a vertex connect sum of such graphs is ...
- 68.8k
4
votes
Minimum planar bipartite graph to cover all perfect matching count
Here is a way to build a balanced, planar, bipartite graph that has exactly $k$ perfect matchings and $O(\log^2 k)$ vertices. First, notice that a ladder graph on $2n$ vertices has exactly $F_n$ ...
- 567
4
votes
Accepted
Planar graph of high valence
Here is another solution, with weaker assumptions. Suppose G tessellates a $k$-gon, where all internal vertices have valence at least 6, and the vertices of the $k$-gon have valence at least 4. Take 2 ...
- 1,617
Only top scored, non community-wiki answers of a minimum length are eligible