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,008
questions
2
votes
1
answer
48
views
Maximum number of vertices with degree three in maximal bipartite planar graphs
A bipartite graph $G$ is a graph where each cycle has an even length. If $G$ can be drawn on the plane without any crossings of edges, $G$ is called planar. $G$ is called maximal planar bipartite if ...
- 1,978
2
votes
1
answer
35
views
Inductive proof for statement about product of weights in intro to dimer model
I was reading this review by Kenyon on the dimer model, and there's a lemma at the beginning that I'm struggling to prove.
Here's the set-up. We have a finite 2D square lattice graph, bounded by a ...
- 31
1
vote
0
answers
33
views
An example of Dessin d'Enfants
I'm self-studying the book of Graphs on Surfaces and Their Applications, Lando & Zvonkin.
In Sec 2.3, we assume the form of an underlying polynomial in the Fig.2.20 below as
$$
f(x) = K \frac{(x - ...
- 493
5
votes
1
answer
179
views
Why does a 3-regular planar graph of diameter 3 have at most 12 vertices?
Today, I saw an interesting exercise on page 224 of the West textbook "Introduction to Graph Theory".
6.1.15. Construct a 3-regular planar graph of diameter 3 with 12 vertices. (Comment: T. ...
- 1,978
2
votes
2
answers
116
views
Heptagon is divided into pentagons and hexagons. Prove that there are at least $27$ pentagons in this division.
A heptagon is divided into convex pentagons and convex hexagons in such a way that each vertex of the heptagon is the vertex of at least three polygons of the division.
Prove that there are at least $...
- 1,047
1
vote
0
answers
67
views
Proof of $e\leq3v-6$ for planar graphs without Euler's formula
For a short talk for an audience not familiar with graph theory I want to give an informal proof that $e\leq3v-6$ holds in all planar graphs with $v>2$ and I don't want to use Euler's formula. My ...
- 6,509
1
vote
0
answers
65
views
Concise yet Rigorous Proof: How to Modify It?
The following proposition is standard.
Proposition 1. Let $G$ be a graph with a planar drawing $D$ and at least three vertices. Then, $D$ can be extended to a multi planar drawing $D^*$ by adding ...
- 1,978
6
votes
1
answer
121
views
Connectivity vs. Simplicity in planar graphs
Let $G$ be a simple plane graph where each face is either a triangle or a quadrilateral. Now, for each quadrilateral face $f$ of $G$, we insert a pair of crossing edges into $f$ to obtain $G'$. For ...
- 1,978
0
votes
0
answers
13
views
Maximal planar graphs with minimum independent sets
The lower bound is known to follow immediately from the Four Color Theorem.
Theorem 1. If $G$ is a planar graph with order $n$, then $\alpha(G) \geq \frac{n}{4}$.
The lower bound in Theorem 1 is sharp....
- 1,978
1
vote
0
answers
38
views
How best to model "stream puzzle" games?
A number of puzzle games around the 00s had mechanics based around manipulating streams of objects towards sinks on a grid map, with the level being passed when a certain number of objects had been ...
- 610
1
vote
1
answer
44
views
Degenerate Schläfli symbols involving 1
I understand that Schläfli symbols with integral elements $\{p,q\}$ both greater than or equal to $2$ represent planar graphs (multigraphs if $p$ is $2$), and these graphs, if finite, represent ...
- 13
0
votes
1
answer
49
views
The number of surfaces between connected components in higher dimensions
Let $C_1, \ldots, C_K$ be the collection of $K$ disjoint subsets (I'll call them components) of $\mathbb R^d$ so that:
Each $C_i$ is connected and open.
$\cup_i cl(C_i) = \mathbb R^d$, where $cl$ is ...
- 635
0
votes
1
answer
34
views
In a planar embedding of a graph, can vertices lie on each other? [closed]
I am wondering if vertices of a planar graph can lie on top of each other in an embedding of the graph. Also, when drawing a picture/representation of the graph, is drawing vertices on top of vertices ...
- 31
0
votes
1
answer
40
views
Why is a non-planar graph still non-planar after subdividing it?
A graph $H$ is said to be a subdivision of a graph
$G$ if $H$ can be obtained from G by successively deleting an edge in $G$, and replacing that edge with a length
2 path (whose central vertex was not ...
- 1,673
0
votes
0
answers
38
views
Can a vertex lie on an edge in a planar graph?
I am wondering if a vertex can lie on an edge in a planar graph- I am not sure if an edge of this vertex is regarded as crossing the edge on which the vertex lies. I have two questions here:
Is the ...
- 1,673
34
votes
1
answer
3k
views
Euler's formula doesn't work for null graph?
Given the null graph with no edges or vertices, we have a connected planar graph as no edges cross when this graph is drawn in the plane, and the fact that any two distinct vertices have a path ...
- 1,673
0
votes
0
answers
32
views
Are the edges of a planar graph part of its faces? (Graph Theory)
The definition of face I have learned for planar graphs is "a region where any 2 points in it not on $G$ can be connected by a line which doesn't intersect any of the edges of $G$". I am ...
- 1,673
1
vote
1
answer
53
views
How is the face for a tree graph bounded by any sides at all? (Graph theory) [closed]
I have learnt that every face in a planar graph has sides, and that sides are edges which bound the face clockwise. I am very confused about a few things regarding sides:
I am not seeing how the ...
- 1,673
0
votes
0
answers
53
views
What is "the plane" in graph theory?
I have learnt that a planar graph is a graph which can be drawn on the plane without any of its edges crossing. What exactly is "the plane"? In plane geometry, we define a plane to be a flat ...
- 1,673
0
votes
0
answers
17
views
Dual graph relation to star-mesh duality
I'm confused about the realtionship between dual graphs and the so called star-mesh transformation: https://en.wikipedia.org/wiki/Star-mesh_transform.
Take a simple triangle, its dual graph looks like ...
0
votes
0
answers
37
views
A graph coloring game of merging subgraphs
A graph coloring game
This is a 2-player game played by players $A$ and $B$. A random non-trivial planar connected graph $G(V,E)$ is chosen. Player $A$ sets up the game as follows:
Player $A$ ...
- 3,133
3
votes
0
answers
58
views
Bound number of loopless multigraphs
Let $d_1,\dots,d_n\geq 0$ be integers and let $G_{d_1,\dots,d_n}$ denote the set of loopless multigraphs with this degree sequence. I want to prove the following bound on the number of such ...
- 1,465
0
votes
0
answers
26
views
Number of vertices in spherical embeddings with large stars.
Suppose I am given a spherical embedding of a graph, specifically a triangulation, onto the unit sphere such that all edges are short geodesics (lengths strictly smaller than $\pi$). Let us further ...
- 549
0
votes
1
answer
18
views
Are Apex graphs always Toroidal?
An Apex graph is a grpah that is either Planar, or can be made planar by removing a single vertex.
Are all Apex graphs Toroidal?
- 796
1
vote
0
answers
24
views
Structural characterizations of planar graphs
I'm looking for as many characterizations of planar graphs, preferably those that are more `structural'. Wagner's and Kuratowski's results get close, but the characterizations of Whitney and Maclane ...
2
votes
1
answer
204
views
4-color coloring game.
Similar to this question.
5-color coloring game.
Let there be two players, $𝐴$ and $𝐵$, and a map.
They now play a game such that:
Player $𝐴$ picks a region and player $𝐵$ colors it such that the ...
- 796
1
vote
1
answer
50
views
For what values of $n$ $(n\ge 3)$ is the graph $C_n \times P_n$ planar?
First instinct was that maybe the new graph won't be planar for $n=3$ and $n=5$ because then it might contain a subgraph that is isomorphic to $K_3,_3$ or $K_5$, but I am not sure how to prove that. ...
- 31
3
votes
0
answers
29
views
Generalization of Triangulations in Graph Theory
There are some results on planar triangulations I was trying to generalize to a larger class of graphs.
So, what I am looking for is, a set of graphs such that the intersection of this set and the set ...
2
votes
1
answer
38
views
Suppose a tree graph T with $n\ge 4$ ,and 3 edges $e_1,e_2,e_3$ from its complement tree graph T-.Show that $G = T + e_1 + e_2 +e_3$ is a planar graph
can't seem to find the proof for this problem.
I know that a Tree graph has the property: $n = m - 1$ where $n$ is the number vertices and $m$ is the number of edges.
Also not sure if the restriction ...
- 31
0
votes
1
answer
47
views
Showing inequality about number of vertices with ceratin degree for planar graphs
I am currently struggling on showing the following inequality for planar graphs without loops. Let $\delta(G) \geq 3$ and $\tau_i$ be the number of vertices with degree $i$, then:
$$
\tau_5 + 2 \tau_4 ...
- 583
1
vote
0
answers
14
views
Related between Kuratowski theorem and any graphs that $\chi(G)\leq 4$ and $\chi(G)\leq 5$
Is there related between Kuratowski's theorem and any graphs that $\chi(G)\leq 4$ and $\chi(G)\leq 5$ (chromatic number)?
- 463
3
votes
1
answer
86
views
Construct a class of maximal planar graphs with exactly 4 vertices of degree 3.
The post is very interesting, and it tells us that any planar graph with at least $4$ vertices has at least $4$ vertices of degree $5$ or less. Recently, I also saw a question on a Chinese forum (...
- 1,978
0
votes
0
answers
38
views
e <= 3v - 6 for planar graph question: why does every face (of a planar graph) have to have at least three sides?
Can't we make a face with just two edges(sides) and two vertices? We just connect those two vertices twice each with different edges and we can make a face between the two edges with only two vertices ...
0
votes
3
answers
82
views
Could there exist a planar graph with the following degrees of vertices: {5, 5, 4, 4, 4, 2} [closed]
I was wondering if a graph existed because I used euler's inequality and it said that theres supposed to be a graph but im having a hard time figuring out what it is. Thank you!
- 11
1
vote
1
answer
32
views
Asymmetric graphs with asymmetric edge-deleted subgraphs
When I say graph, I mean undirected, irreflexive graphs without multiple-edges (sometimes called a simple graph).
Call a graph $G$ “asymmetric” if the only automorphism of $G$ is the identity map. For ...
- 2,471
3
votes
1
answer
64
views
Find segment x on the secant circles below
In the figure determine $'x'$ , knowing that $PM=MQ=4$ and $O$ and $O'$ are centers.(S:$x=4$)
I try:
$\triangle OQH \sim \triangle OAP \implies \dfrac{HO}{OP} = \dfrac{HQ}{AP} = \dfrac{8+OP}{AO}$
$\...
- 5,881
9
votes
2
answers
138
views
A periodic layout for the Petersen graph
The Petersen graph is a well-known graph with genus $1$, which means it can be drawn without crossings on a torus. Here is one possible embedding of this type. Topologically, we can think of a torus ...
- 134k
0
votes
0
answers
20
views
Inverse of image connected component graph labeling
For a given image I one can compute connected components and define a graph structure G on those components. Each connected ...
- 263
1
vote
2
answers
88
views
Does a maximal planar graph with number of vertices $\ge$ 6 always have a vertex of degree exactly 5?
In a proof of a theorem, my professor wrote that since $G$ is a maximal planar graph with $|V|\ge6$, so, there exists a vertex of degree 5. I know the result that every planar graph has a vertex of ...
- 668
0
votes
0
answers
44
views
Given a directed graph, can you determine if it can be drawn as a planar graph?
Say a directed graph has loops and has nodes directed towards each other.
I would like to know if there is an algorithm for determining if the graph can be drawn as a planar graph.
- 185
0
votes
0
answers
32
views
Given several $a_i$-$r$ paths in a planar graph how ``balanced" of a tree rooted at $r$ can I make?
Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and several $a_i$-$r$ paths $P_i$ in a planar graph $G$.
I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ that minimizes the ...
- 278
2
votes
0
answers
30
views
Counting the number of faces of non-connected planar graph
I have a non-connected planar graph with 15 vertices, 20 edges and 3 components. I know the Euler's formula for counting the number of faces in a connected graph, but how do I modify it using the ...
- 29
1
vote
1
answer
88
views
Can we construct a class of planar graphs with minimum degree $5$ (or even $5$-connected planar graphs) with diameter 3?
The diameter of graph is the maximum distance between the pair of vertices.
From the article we know that there is no planar graph of diameter 2 with minimal degree 5. (Thank kabenyuk for informing ...
- 1,978
1
vote
3
answers
98
views
The connectedness of dual graph
Prove: if a planar graph $G$ is $k$-vertex-connected, then so do its dual $G^{\ast}$ for $k=2,3$. And find a counterexample for $k=4$.
I only have a vague idea for $k=2$: if $G$ has a cut vertex, then ...
- 355
0
votes
0
answers
15
views
Overlapping models/minors of planar graphs
Suppose we are given a planar graph $G$ and connected subgraphs $G_1,G_2,..,G_l$ of $G$ such that each $G_i$ intersects (shares a node with) constant many other $G_j$ on average.
Construct a graph $H$ ...
- 278
0
votes
0
answers
31
views
Question about "growing layers of a planar graphs"
Given a planar graph $G$ k nodes $S$ of $G$ construct "layers" $L_i$ for $i=0,1,...$ as follows $L_0=S$, having constructed layers $L_0,L_1,..,L_i$ layer $L_{i+1}$ consists of those nodes ...
- 278
1
vote
0
answers
37
views
Let $n\geq 3$. Is there a connected, planar, bipartite graph with $n$ regions and $n$ vertices?
The answer given is that according to a Corollary of Euler’s formula (Corollary 3 Section 10.7), such a graph has at most $2n − 4$ edges. Applying this to Euler’s formula ($r = m − n + 2$), there are ...
- 11
1
vote
0
answers
80
views
Queue number above 2 for planar graphs?
Are there any known planar graphs with queue number greater than $2$?
The queue number of a graph counts the minimum number of subsets that the edges must be divided into to avoid all nested pairs of ...
- 892
2
votes
0
answers
60
views
Does a quadrangulation with minimum degree $3$ contain either a $(3,3)$ edge or a $(3,4)$ edge$?$
A simple graph $G$ is a quadrangulation of the plane if it can be embedded in
the plane in such a way that all faces are quadrangles. We say an edge $e=(uv)$ is an $(a,b)$-edge if the degrees of the ...
- 1,978
2
votes
1
answer
59
views
Argue that in a planar graph on n nodes there is an independent set of at least n/8 nodes, each of degree at most 11.
I am having troubles with this question. Seems non-trivial as I see it. The tightest lower-bound I could reach was "at least n/12" number of nodes in the independent set, with the assumption ...
- 63