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

947 questions
Filter by
Sorted by
Tagged with
46 views

### Confusion in understanding two equivalent statements of Kuratowski's Theorem

Two graphs G and H are homeomorphic if there is a graph isomorphism from some subdivision of G to some subdivision of H. Kuratowski's theorem: Statement 1: A graph is planar if and only if it does ...
• 638
50 views

### Existence of special planar graphs

In 1989, Faudree proved this theorem: Theorem Let $G$ be a 2-connected graph with $n\ge 3$ vertices. If $|N(x)\cup N(y)|\ge \frac{2(n-1)}{3}$ for any $xy\notin E(G)$, then $G$ is Hamiltonian. ...
• 1,348
63 views

### Planar graph K3,3

I need a little help with graphs in the field of graph theory. I have 3 undirected graphs : A1 = {{x1, x2, x3, x4, x5, x6, x7, x8}, {{x1, x2}, {x1, x3}, {x1, x8}, {x2, x6}, {x2, x7 }, {x3, x4}, {x3, ...
• 63
1 vote
80 views

### Why is the number of undirected strict graphs, s.t. $G(V, E): |V| = 8,~\forall v\in V: \deg(v)=5$, equal to $3$?

Preface I am currently preparing for applied mathematics and informatics olympiad qualifiers in my university, and while preparing I have stumbled upon the following task, which is quite hard for me ...
• 508
37 views

### Computing Longest Simple Path in a Particular Digraph

Let $D$ be a digraph as follows: I want to compute a longest simple path of it. For an acyclic digraph, there is a method I can run in Python that returns a longest path, but $D$ is not acyclic. I ...
• 3,085
47 views

### Is the number of maximal cliques of a planar graph bounded by its number of faces?

I would like to know if there is any relationship between the number of maximal cliques in a planar graph, and its number of faces? It is known that for a planar graph $G$, if $H\subseteq G$ is a ...
• 1,647
80 views

### What is the name of this graph?

By plantri, we know that the following graph is the unique planar graph with 15 vertices of minimum degree 5. I add the graph in The House of Graphs (Graph 49406). But I do not know if it has a name....
• 1,348
54 views

### Planar graph with girth of certain length

Problem: Let $G$ be a planar graph with girth (= length of the shortest cycle in that graph), such that each face, including the outer one is bounded by a cycle. ($G$ does not contain any vertices of ...
• 65
122 views

### Existence of a big connected component in a planar graph

Let $G$ be a connected finite subgraph of $\mathbb{Z}^2$. We know that we can define the dual graph $G^{\ast}$ of $G$ having vertices the faces of $G$ and edges between two vertices at distance $1$ ...
134 views

### Why do we care about planar graphs?

Planar graphs are graphs that can be embedded in the plane. Classic examples of planar graphs are the $1$-skeleton (vertices and edges) of polyhedrons. Most introductory books on graph theory will ...
• 10.4k
80 views

### How to determine if this graph is planar?

I was doing a graph theory text book where one of the problems asks: Is this graph planar? As this graph contains a triangle, the best bound for $e$ is $3v-6$ which this satisfies $(14<18)$ So then ...
• 1,485
34 views

### Causal system giving a non-causal output?

I have just written a Python code ploting DFT's using the convolution product: $$y[t] = u[k] * h[k] = \sum_{k=-\infty}^{+\infty} u[k] h[t-k]$$ I'll take a high resolution so the graph is more precise. ...
1 vote
62 views

### Subgraph $K_5$ (or $K_{3,3}$) [closed]

I'm having trouble with the two graphs below. Graph appears like it will have a $K_5$, however, I can't connect the vertices properly. How do these graphs have a $K_5$ (or $K_{3,3}$)?
• 23
129 views

### Proving or disproving planarity

I'm looking through past exams and am having issues on this problem: Call the graph $G$. My immediate thought is to use brute-force. That is, I want to apply Kuratowski's Theorem and find a subgraph ...
• 772
104 views

### Analogous formula for finding “non-planar graphs” using defined faces instead of edges in $\Bbb R^3$?

Given a graph, along with a set describing which edges are connected to form faces, how could we determine whether it is embeddable in 3D Euclidean space, a.k.a $\Bbb R^3$? What formula applies here? ...
• 101
75 views

### How to prove that the book thickness of the complete 4-partite graph $K_{2,2,2,2}$ is $4$?

A book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. The book thickness $bt(G)$ of a ...
• 1,348
41 views

### How many subgraphs with exactly 6 edges can I make from a complete graph with 7 vertices?

Let the complete graph be unweighted and undirected. The subgraphs can be unconnected. Edit (More detail): I'm trying to go about this by splitting it up into spanning trees and non-spanning trees ...
1 vote
67 views

### Breaking chocolate problem and Euler characteristic.

There is the following Problem: Given an $m \times n$ chocolate bar, where you can only break it along the gridlines and only break one piece at the time. What is the minimum amout of steps needed to ...
• 640
77 views

• 227k
35 views

### Can a penny graph be inflated to uniformly cover a circumscribed circle?

Consider a minimum-distance packing of unit circles (aka pennies) that form a hexagonal tiling. If we restrict our attention to only those pennies that are contained or tangent to a concentric circle ...
• 105
1 vote
100 views

### Is a maximal planar bipartite graph containing cut vertices isomorphic to a star?

A simple graph $G$ is called maximal planar bipartite if it has the property: if we add an edge (without adding vertices) to $G$, we obtain a graph which is no longer planar, bipartite or simple. See ...
• 1,348
51 views

### Determining whether a graph is planar?

Question: If a connected planar graph with n vertices all of degree 4 has 10 regions, determine n. I am a bit confused about how exactly to handle this problem.
1 vote
66 views

• 125