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)...
- 2,474
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 ...
- 4,425
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 ...
- 10.5k
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 &...
- 1,940
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 ...
- 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
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 ...
- 609
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 ...
- 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
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 ...
- 2,474
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. ...
- 2,474
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}$. ...
- 31
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 ...
- 468
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 ...
- 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
51
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
2
votes
1
answer
42
views
Genus of a graph consisting of two faces homeomorphic to open disks
Suppose the graph $G$ is embedded in a surface $Q$ such that there are two faces $F_1,F_2$ of the embedding, each homeomorphic to the open disk, such that each node of $G$ lies on $F_1$ or $F_2$.
Is ...
- 468
2
votes
0
answers
68
views
Using persistent homology to measure the "isotropy" of a graph
Suppose we have a random graph where the positions of the vertices are significant. How can I measure the isotropy of this graph? I may not be using the correct terminology, but essentially, I'm ...
- 3,435
1
vote
1
answer
59
views
what is the maximum number of vertices after a 3D planar and regular polygon was truncated by a 3D box?
Let me use a 3D square as an example first. A 3D planar square has four vertices. If this square was truncated by a 3D box, then I can tell that the maximum number of vertices ($NV_{max}$) is eight, ...
- 141
0
votes
0
answers
17
views
maximum number of edges in a planar graph on 11 vertces with no 5 cycle [duplicate]
It can be checked systematically that the result
ex$_P (n,C_5 )$ ≤ $(12n−33)/5$ holds for n ∈ {11, 12, 13} (this turns out to be not as onerous as
it might at first appear!)
How to compute maximum ...
- 11
0
votes
0
answers
11
views
In a simple weighted planar graph, find the shortest (in terms of total length) set of closed walks that cover all shortest paths
Consider a simple planar graph $g$ embedded in the 2D plane with weights corresponding to Euclidean distances, and let $P$ be the set of all its shortest paths $p$.
I want to find a set $W$ of at most ...
3
votes
2
answers
319
views
Prove or Disprove: Is there a connected planar graph with an odd number of faces where every vertex has a degree of 6?
Prove or Disprove: Is there a connected planar graph with an odd number of faces where every vertex has a degree of 6?
I know,
Theorem: In a connected planar graph where each vertex has the same ...
- 69
2
votes
1
answer
339
views
Can a connected planar graph have 10 vertices and edges? is this possible?
Can a connected planar graph have 10 vertices and edges? is this possible?
Using Euler’s formula, $V − E + F = 2$.
$10 − 10 + F = 2$,
Therefore $F = 2$.
Do I also need to use this formula: $2E$ $\geq$ ...
- 69
3
votes
0
answers
35
views
consistent vertex configurations for Archimedean tiling
I am trying to find if there is a simple rule for vertex configurations $n_1.n_2\ldots n_k$ that define Archimedean tilings (equivalently called uniform/semi-regular/vertex-transitive tilings). In ...
- 576
3
votes
1
answer
39
views
Simple graph $G$ can be represented as union of $2$ edge-disjoint graphs
I'm trying to prove the following statement:
Prove that any simple graph $G$ can be represented as the union of $2$ edge-disjointed graphs $G_{1}$ and $G_{2}$, where $G_{1}$ is acyclic and $G_{2}$ ...
- 367
2
votes
1
answer
241
views
Constructing infinite 3-connected quadrangulations containing only induced 4-cycles and induced 6-cycles.
Quadrangulations are planar graphs such that every face is of length 4.
We can construct infinitely many quadrangulations that contain only induced 4-cycles(the length of every induced cycle is at ...
- 2,474
3
votes
1
answer
34
views
Is There any Untraceable Generalized Petersen Graph?
The Petersen graph is one of the example of graph which is not Hamiltonian.
Can we find an example among the generalized Petersen graph which doesn't have Hamiltonian path (untraceable)?
- 1,949
1
vote
1
answer
68
views
Does this graph contain a subdivision of $K_5$ or $K_{3,3}$?
I'm working on graph theory and I've encountered a challenge in determining whether a given graph contains a subdivision of $K_5$ or $K_{3,3}$, which would imply that the graph is non-planar by ...
- 109