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
0
votes
0
answers
15
views
What is the toughness of Tutte graph?
Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte.
Let $c(G)$ denote the number of components of a graph $G$.
If $G$ is not complete, the toughness of $G$ $$\tau(G)...
1
vote
0
answers
50
views
Can we use calculus for graph theory?
I was thinking about how to specify an algorithm for planarity of a graph. The obvious very direct (but inefficient) approach would simply be to try to position the vertices at every possible point ...
3
votes
0
answers
58
views
+50
Which graphs can be represented as adjacencies in a rectangular subdivision?
The TL;DR version:
Is there a simple characterization of graphs representable by adjacencies of a subdivision of a rectangle into smaller rectangles?
Now the longer version:
I am working on a ...
6
votes
1
answer
206
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 &...
4
votes
2
answers
84
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 ...
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 ...
1
vote
0
answers
33
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
62
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 ...
0
votes
0
answers
31
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 ...
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 ...
2
votes
1
answer
80
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 ...
1
vote
1
answer
55
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. ...
3
votes
2
answers
64
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}$. ...
3
votes
1
answer
290
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 ...
1
vote
0
answers
43
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 ...