Skip to main content

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
22 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)...
licheng's user avatar
  • 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 ...
zooby's user avatar
  • 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 ...
templatetypedef's user avatar
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 &...
hellofriends's user avatar
  • 1,950
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 ...
ninaPh99's user avatar
  • 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 ...
Hao S's user avatar
  • 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 ...
Intruder.guru's user avatar
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 ...
NTc5's user avatar
  • 609
0 votes
0 answers
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 ...
licheng's user avatar
  • 2,474
1 vote
1 answer
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 ...
Chard's user avatar
  • 309
2 votes
1 answer
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 ...
licheng's user avatar
  • 2,474
1 vote
1 answer
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. ...
licheng's user avatar
  • 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}$. ...
nevikw39's user avatar
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 ...
Hao S's user avatar
  • 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 ...
dekats's user avatar
  • 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$...
Abhimanyoo Karve's user avatar
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 ...
ComptonScattering's user avatar
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 ...
ninaPh99's user avatar
  • 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 ...
Hao S's user avatar
  • 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 ...
sam wolfe's user avatar
  • 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, ...
Tingchang Yin's user avatar
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 ...
user528305's user avatar
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 ...
schmuelinsky's user avatar
3 votes
2 answers
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 ...
Glo's user avatar
  • 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$ ...
Glo's user avatar
  • 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 ...
Tomáš Bzdušek's user avatar
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}$ ...
Victor Feitosa's user avatar
2 votes
1 answer
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 ...
licheng's user avatar
  • 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)?
user966's user avatar
  • 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 ...
neo's user avatar
  • 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 ...
licheng's user avatar
  • 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 ...
KnarfB's user avatar
  • 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 ...
graphtheorybeginner's user avatar
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 ...
SLLegendre's user avatar
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 ...
Mailbox's user avatar
  • 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 ...
Lawton's user avatar
  • 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 ...
Binyamin Riahi's user avatar
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} ...
RandomMatrices's user avatar
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 ...
licheng's user avatar
  • 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", ...
SleepyMemory's user avatar
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 ...
Tomais's user avatar
  • 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 ...
Simd's user avatar
  • 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 $...
impressive305's user avatar
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 ...
SleepyMemory's user avatar
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 ...
Conor_Meise's user avatar
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. ...
impressive305's user avatar
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 ...
Keven McFlurry's user avatar
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 ...
licheng's user avatar
  • 2,474
1 vote
0 answers
43 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 ...
Sean's user avatar
  • 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 ...
An5Drama's user avatar
  • 416

1
2 3 4 5
22