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