# 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
Filter by
Sorted by
Tagged with
22 views

• 1,950
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
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
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 ...
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
34 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
32 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
83 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
56 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
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
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
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
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$...
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 ...
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
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
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
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, ...
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 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 ...
322 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
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
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 ...
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}$ ...
244 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
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
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
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
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
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 ...
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
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
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
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 ...
21 views

### Computing maximum of a ratio defined on the grid graph

Consider an $n \times n$ grid graph $G$. Define the following quantity $$m(G) = \text{max}\bigg\{\frac{|E|_{H'}}{|V|_{H'}},~ H' \subseteq G, ~~|V|_{H'} > 0 \bigg\},$$ ...
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
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", ...
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
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
40 views

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