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
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
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 ...
- 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
242
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
2
votes
0
answers
79
views
Are Tutte's results still valid for planar graphs with multiple edges?
Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner ...
- 2,474
1
vote
1
answer
61
views
Symmetries in regular "floral" circle patterns (seed of life etc.)
Consider $n$ equally sized circles $c_i$ in the plane with their centers $x_i$ in the vertices $v_i$ of a regular $n$-gon and all meeting in the center of that $n$-gon.
Examples:
Fig. 1: circle ...
- 21
1
vote
0
answers
28
views
If we have a planar graph, why is it true that there always exists a vertex such that $deg(v) \leq 3$ or a face $f$ such that $deg(f) \leq 3$? [duplicate]
If we consider $G$ to be a planar graph with no loops or multiple edges, there exists a vertex $v \in V(G)$ such that $deg(v) \leq 3$ or there exists a face that $deg(f) \leq 3$.
I'm not entirely sure ...
14
votes
10
answers
3k
views
Can you explain to me why this proof by induction is not flawed? (Domain is graph theory, but that is secondary)
Background
I am following this MIT OCW course on mathematics for computer science.
In one of the recitations they come to the below result:
Official solution
Task:
A planar graph is a graph that can ...
- 294
1
vote
1
answer
69
views
Are all 2-connected graphs planar?
I know that all trees are planar, and so now I'm wondering whether 2-connected graphs are necessarily planar. I would imagine that this is true given that all 2-connected graphs have an ear ...
- 927
2
votes
1
answer
88
views
What is the shortest path that visits every node and edge in the dodecahedral graph?
The dodecahedral graph is the Platonic graph corresponding to the connectivity of the vertices of a dodecahedron, with 20 nodes and 30 edges. Assuming all edges have a length (weight) of 1, I want to ...
- 1,861
0
votes
1
answer
73
views
Irrigation problem as a graph coloring problem
I am trying to solve an interesting problem in graph coloring which I believe is related to the vertex cover problem.
The graph is a $12 \times 12$ grid, representing a field. The field needs to be ...
- 137
0
votes
0
answers
21
views
Computing maximum of a ratio defined on the grid graph
Consider an $n \times n$ grid graph $G$. Define the following quantity
\begin{equation}
m(G) = \text{max}\bigg\{\frac{|E|_{H'}}{|V|_{H'}},~ H' \subseteq G, ~~|V|_{H'} > 0 \bigg\},
\end{equation}
...
- 545
0
votes
1
answer
37
views
Does the operation stitch preserve non-Hamiltonicity?
A planar graph is triangulated if its faces are bounded by three edges. A triangle of a planar graph is a separating triangle if it does not form the boundary of a face. That is, a separating triangle ...
- 2,474
0
votes
1
answer
65
views
Overlapping bridges on graphs
I have trouble understanding the first part of proof of the Theorem 10.25 of Bondy and Murty's textbook. The Theorem states "Overlapping bridges are either skew or equivalent 3-bridges", ...
- 13
0
votes
0
answers
39
views
Sequence of degrees of a graph with two colors
With respect to the graph
Another concept central to an understanding of fractional isomorphism is that of the iterated degree
sequence of a graph. Recall that the degree of a vertex $v\in G$ is the ...
- 509
-2
votes
1
answer
61
views
How many different undirected, planar, connected graphs are there where every edge is in a 3-cycle? [closed]
I am interested in undirected, planar, connected graphs where every edge is in a 3-cycle. If there are 4 vertices then, up to isomorphism, there are two such graphs.
How many are there for 5 ...
- 437
1
vote
1
answer
40
views
Proving that G must have an area bordered by maximum of 5 edges
I am working on this proof about planar graphs:
Let G be a planar and connected Graph where every node has a degree higher than or equal to $3$. Show that G must have an area bordered by a maximum of $...
0
votes
1
answer
52
views
Particular examples of dual graphs
What is the dual graph (in the planar sense) of a totally disconnected graph on more than one vertex? I can't figure it out, considering that the graph is planar and the dual should be still well ...
- 13
2
votes
0
answers
67
views
Non-planar electrical circuit graph
In the following electrical circuit the textbook says it is non-planar. I was curious from a mathematics perspective on how to approach this and found Kuratowski's Theorem about having a K5 or K3,3 ...
- 195
0
votes
1
answer
51
views
Number of squares in a planar Graph [closed]
I need help with the following Graph Theory problem:
Let $G$ be a connected and planar Graph. Each area in the planar version of the Graph (including the outer area) is either a square or a hexagon. ...
0
votes
0
answers
18
views
Combinatorial isomorphisms of 2-connected plane graphs are topological
In Diestel Theorem 4.3.1 (ii) it says "Every combinatorial isomorphism between two 2-connected plane graphs is topological."
I don't understand, where in the proof do we use the fact that ...
- 107
0
votes
1
answer
106
views
Does 'Homeomorphism' describe Kuratowski's theorem accurately?
Let $G=(V,E)$ be a graph.
The edge subdivision operation for an edge $\{u, v\} \in E$ is the deletion of $\{u, v\}$ from $G$ and the addition of two edges $\{u, w\}$ and $\{w, v\}$ along with the new ...
- 2,474
1
vote
0
answers
42
views
Can we take gradient of a curve?
Consider the case of planar curves in $\mathbb{R}^2$. They can be described by a function $f(x,y) = 0$. For example, a circle can be described by $x^2+y^2=1$. We can take the gradient of this function
...
- 101
0
votes
0
answers
65
views
The final step of proving Kuratowski’s Theorem
Recently when I read the proof of the Kuratowski’s Theorem, I was stuck at the final step where it States 4 cases (Since this proof uses many lemmas, it is difficult to give one context related with ...
- 416