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
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