Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with planar-graphs
Search options not deleted
user 9025
graphs that can be embedded into the plane, i.e. that can be drawn without crossings between the lines representing edges.
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
4
votes
Accepted
Generating 12-vertex plane graphs with 2 faces of degree 3 and all other faces of degree 4
The conditions "max face = 4, 21 edges, 12 vertices" characterize them. So:
plantri -pf4e21 12 -- 125 outputs (these are the 3-connected ones)
plantri -pf4e21c2 12 -- 120857 outputs (these are the 2- …
- 37.7k
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
1
vote
Accepted
Two ears polygon in a maximal planar hamiltonian graph
Carol Zamfirescu and Gunnar Brinkmann have informed me that this paper answers the question.
- 37.7k
3
votes
Accepted
Sufficient condition for a Hamilton cycle $C$ in a planar triangulation $G$ s.t. every trian...
Gunnar Brinkmann informs me that this paper constructs planar triangulations where every hamiltonian cycle misses all the edges of many triangles. Some of the examples are even 5-connected.
- 37.7k
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
2
votes
Enumerating all inequivalent planar embeddings of a planar graph
(Too long for a comment). Note that there are two different ways to define "all the embeddings" of a graph, both completely natural. I'll illustrate by example. Suppose a graph consists of two triangl …
- 37.7k