All Questions
Tagged with planar-graphs graph-theory
955
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
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 ...
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 ...
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
81
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 ...
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 ...