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,083
questions
6
votes
1
answer
195
views
How to find a formula for the terms of this sequence?
I saw a problem on this forum concerning the number
$$T = 1 + \frac{2 +\frac{3+ \frac {4+...}{5+...}}{4+\frac{5+...}{6+...}} }{3 + \frac{4+\frac{5+...}{6+...}}{5+\frac{6+...}{7+...}}}$$
whose rule is &...
- 1,897
4
votes
2
answers
79
views
Maximizing Edge Weights in Planar Graphs with Vertex Weights Summing to One
Let $G$ be a planar graph where we assign a non-negative real number to every vertex
of $G$ such that the sum of these numbers is $1$. Then, we assign to every edge the product of the numbers at the ...
- 123
0
votes
0
answers
16
views
Dipping into sets of parallel edges in graph drawings
Given a multigraph embedded in the plane call a maximal set of parallel edges between $u,v$ such that only one of the induced faces contains nodes besides $u$ or $v$ a topologically parallel set (tell ...
- 468
1
vote
0
answers
32
views
Degree of the neigbour verticies of a vertex degree 5 in a planar graph - visualization
I'm writing a lecture on 5-coloring planar graphs and I'm having trouble visualizing this inequality form the proof
"$2n_5 \leq \sum_{d \geq 12} dn_d$"
I want to make a simple drawing of ...
4
votes
1
answer
61
views
Every binary tree with $n$ leaves has a subtree with $k$ leaves where $\frac{n}{3} \leq k \leq \frac{2n}{3}$.
I want to show the following:
Every binary tree with $n$ leaves has a subtree with $k$ leaves where $\frac{n}{3} \leq k \leq \frac{2n}{3}$.
My approach:
First thing I did was to draw a binary tree and ...
- 609
0
votes
0
answers
28
views
Does there exist a 5-connected planar graph that is perfect?
In a previous post, I proved that no 5-connected maximal planar graph is perfect.
My proof, with slight modifications, can show that if a maximal planar graph with minimum degree 5 is perfect, then ...
- 2,474
1
vote
1
answer
31
views
Graph operations that preserve the number of spanning trees
I am not working on graph theory, so my question may be a little bit vague.
Given a graph (directed or undirected), are there any operations (adding/contracting/removing/sliding edges, gluing with ...
- 309
2
votes
1
answer
78
views
Does there exist a 5-connected maximal planar graph that is perfect?
A graph $G$ is said to be perfect if $\chi(H)=\omega(H)$ hold for any
induced subgraph $H_i\subseteq G$ (and so for $G$ itself, too)
For maximal planar graphs with connectivity 3, it is easy to ...
- 2,474
1
vote
1
answer
52
views
Are there examples of non-perfect graphs among these graphs
A graph $G$ is said to be perfect if $\chi(H)=\omega(H)$ hold for any
induced subgraph $H_i\subseteq G$ (and so for $G$ itself, too)
Start with a simple planar graph $H$ where every face is a 4-cycle. ...
- 2,474
3
votes
2
answers
62
views
Prove or disprove that this graph is planar
I need to show whether the following graph $G$ is planar or not.
At my first glimpse, it looks like a non-planar graph. Nevertheless, I couldn't find any subgraph homeomorphic to $K_5$ or $K_{3,3}$. ...
- 31
3
votes
1
answer
286
views
Problem related to crossing number
Let $G$ be a graph embedded in the plane (with crossings). For $ F \subset E(G) $, denote by $c(F)$ the set of edges of $G$ that cross some edge in $F$.
Denote $\delta(v)$ the set of edges with one ...
- 468
1
vote
0
answers
42
views
A planar graph has no bridges and no pair of faces share multiple edges. Then it has two faces with the same number of edges.
A planar graph $G$ has no bridges and no two faces have more than one common edge.
Prove that $G$ has two faces that have the same number of edges.
Attempt:
We can use the Euler characteristic ...
- 11
2
votes
1
answer
60
views
Number of edges in planar bipartite graph.
Suppose G=(V,E) is a planar bipartite graph such that $V_1$ and $V_2$ are the partite sets. Suppose for all $a \in V_1$, $deg(a)\le p$ and for all $b \in V_2$, $deg(b)\le q$. If $|V_1|=x$ and $|V_2|=y$...
0
votes
1
answer
28
views
Determining whether cellulation has "even" property
Is there a $\mathrm{poly}(N)$ algorithm for determining whether an arbitrary cellulation of a $2D$ plane has the following property:
There exists at least one non-empty subset $S$ of the cells such ...
2
votes
1
answer
47
views
Every planar graph with no cycles of length $3,4,5$ is $3$-colorable.
I'm trying to prove that every planar graph with no cycles of length $3,4,5$ is $3$-colorable.
However, I have no opportunity to receive any validation or correction on it, but it would be very ...
- 123