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

Filter by
Sorted by
Tagged with
3 votes
1 answer
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
0 votes
1 answer
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
3 votes
1 answer
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
1 answer
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 ...
2 votes
2 answers
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 votes
1 answer
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 ...
4 votes
0 answers
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
2 votes
1 answer
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
3 votes
1 answer
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$ ...
user avatar
5 votes
1 answer
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
4 votes
1 answer
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
2 votes
1 answer
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. ...
user avatar
1 vote
1 answer
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
4 votes
2 answers
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
3 votes
1 answer
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? ...
2 votes
1 answer
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
0 votes
1 answer
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
1 answer
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
4 votes
1 answer
77 views

Can every planar graph be represented as a set of regions on the grid

Given a planar graph, can you draw a set of connected regions on a grid such that two cells are adjacent if they touch vertically or horizontally, and two regions $A,B$ are adjacent if $A$ has a cell $...
user avatar
0 votes
0 answers
22 views

What are the steps for capturing and redrawing a SVG using Fourier Transform to calculate coefficients?

In a YouTube video (https://www.youtube.com/watch?v=r6sGWTCMz2k), between 20:35 and 21:10, the author 3Blue1Brown mentions, "When I'm rendering these animations, that's exactly what I'm having ...
1 vote
0 answers
42 views

Proof of the Sum of Degrees of Regions Theorem for a planar graph [closed]

I'm studying graph theory and came across the following theorem: For a planar graph $G = (V,E)$, $$\sum_{R \in \mathrm{regions}(G)} \deg(R) = 2|E|$$ Can someone help me prove this theorem? Is this ...
  • 21
-2 votes
1 answer
68 views

Confused about the proof for a theorem in graph theory [closed]

The theorem states the following: Every planar graph can be 5-colored. He starts the proof by saying one can only consider connected planar graphs only. Why? And can anybody give me a hint on how ...
  • 128
0 votes
1 answer
25 views

Find upper bound of planar $f(g, n)$(no cucles of length less than $g$) interms of $g$ and $n$ by using Euler's formula. [duplicate]

Let $g \in \mathbb{N}$ be an integer, where $g \geq 3$. Let $f(g, n)$ denote the maximum number of edges in a planar graph on $n$ vertices if the graph has no cycles of length less than $g$. How to ...
  • 159
3 votes
0 answers
20 views

Algorithm to find minimum edge weights on planar graph in unit plane

Suppose I have planar graph with a fixed number of vertices and edges. Each vertex must be located at a unique integral point on the unit plane ( $(0,0), (1,1), (1,0)$, etc), and each edge must be a ...
  • 926
1 vote
1 answer
61 views

About $k$-ring in planar graph

I am a student currently doing some research on the Four Color Theorem. I mainly studied the paper Efficiently Four-coloring Planar Graphs. In this paper, the authors define $k$-ring as follows: A $k$...
  • 111
0 votes
0 answers
13 views

Find sequence of point from $u$ to $v$ such that each is at distance $d(u,v) = t$ with $t \in [1,2]$.

The problem is the following: Given $n$ points in $\mathbb{R^2}$, give an algorithm that given points $u$ and $v$, $u \neq v$ find a sequence of points such you can go from $u$ to $v$ and in each step ...
1 vote
0 answers
13 views

In planar graph, for any vertex v, it's possible to find an embedding in which v is in unbounded face [duplicate]

As mentioned in title, I am wondering.. Assume G is a planar graph and pick any vertex v. Is is possible to find a planar embedding in which v is in an unbounded face? What if we add a constraint ...
1 vote
1 answer
25 views

Convert a nonplanar graph into a planar one

Is there a way to convert a nonplanar graph into a planar one, but instead of deleting edges, the only allowed action is to add nodes
4 votes
1 answer
66 views

How to construct a planar graph (or a class of planar graphs) with minimum degree 5 of diameter 2?

A subset $D$ of the vertices of a graph G is called a dominating set if every vertex of $G - D$ is adjacent to a vertex of $D$, and the domination number of $G$, denoted $\gamma(G)$, is the minimum ...
  • 1,348
2 votes
1 answer
40 views

Crossing number of 3-regular graphs

What's the largest possible crossing number for a $3$-regular graph? And what about the largest crossing number for a $3$-regular Hamiltonian graph?
0 votes
0 answers
44 views

Ordered sequences of edges such that vertices appear an even number of times

Given an undirected graph with an edge set $E$, and where an edge is an unordered pair of vertices, how many ordered sequences of size $L$ of edges from $E$ exist such that all the vertices that are ...
2 votes
0 answers
51 views

Show that a graph has at least two different dual graphs

If I have a planar Graph $G(V,E)$, it is easy to obtain the dual $G^{*}$ graphically. But how is it possible to show formal that $G$ has at least two different dual graphs? Is it enough to find an ...
  • 57
2 votes
0 answers
54 views

Vertex minors of line graphs

(Vertex Minor) A graph H is a vertex minor of G if H can be obtained from G by a sequence of vertex deletions and local complementation (Local complementation) A local complementation $\tau_v$ is a ...
  • 280
0 votes
1 answer
32 views

Optimize distances between vertices in graph theory

So imagine that I have a weighted graph with some random values ranging between $1$ and $20$, where this integer represents the amount of time required to travel to the node/vertex. I wanted to know, ...
2 votes
1 answer
71 views

Local equivalency of ring graphs and 2xn grid graphs

This question has also been posted in theoretical computer science stack exchange (Local complementation) A local complementation $\tau_v$ is a graph operation specified by a vertex $v$, taking a ...
  • 280
0 votes
0 answers
23 views

Intuition Behind Length of Face in Planar Graphs

I want to be sure that I am understanding the intuition about this observation about planar graphs. In a planar graph, every non-cut edge (non-bridge) appears on the boundary of exactly two regions/...
3 votes
1 answer
144 views

Why is the number of edges of a $C_5$-free planar graph with $n$ vertices at most $\frac{12n-33}{5}$ where $n\in\{11,12,13\}$?

Let us say that a graph is $C_5$-free if it does not contain any cycle $C_5$ as a subgraph (whether induced or not). We define $ex_{_\mathcal{P}}(n,C_5)$ to be the maximum number of edges possible in ...
  • 1,348
1 vote
1 answer
41 views

Find amount of vertice of grade 3 or 4 in planar graph

A planar, loop free connected graph has 8 vertices of either degree 3 or 4 7 faces How many of the vertices are either degree 3 or 4 Since its a planar graph I ...
  • 65
2 votes
1 answer
64 views

Do "possible face sets" of planar graphs satisfy the exchange property?

Given a finite planar graph $\mathfrak{G}=(V,E)$, let $Cyc(\mathfrak{G})$ be the set of all cycles in $\mathfrak{G}$. For each planar embedding $f$ of $G$, let $Face(f)$ be the subset of $Cyc(\...
0 votes
1 answer
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
1 answer
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
0 votes
1 answer
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
0 answers
66 views

Why is the Euler characteristic of a planar graph 2 rather than 1?

According to wikipedia, the Euler characteristic of planar graph is $2$. I'm confused about why this would be true, since for any simple polygon drawn with $n$ vertices we have $e=v=n$ and $f=1$, so $\...
  • 10.1k
3 votes
1 answer
75 views

Isomorphism of two different planar coverings in $S^2$

Let $G$ be a simple graph and $F$ be a closed surface. I will say that two embeddings $f_1 : G \to F$ and $f_2 : G \to F$ are equivalent if there is a homeomorphism $h$ of $F$ and an automorphism $\...
  • 125
4 votes
2 answers
77 views

Proving a chromatic number upper bound for a graph with a planar subgraph

I have the following problem: Let $G$ be a graph such that for any partition of its vertices into two sets, the induced subgraph on either of the sets is going to be planar. Prove that $\chi(G) \leq ...
  • 125
1 vote
1 answer
72 views

How to determine whether a given graph is planar or not?

We are given a graph $G$: After struggling for hours, I think it may be planar. If it is, I couldn't realize how to determine a proper drawing. Things I've tried: Finding a subgraph isomorphic or ...
2 votes
1 answer
56 views

For every 3-regular graph $G$ there exists a 3-regular planar graph $G'$ such that $C(G) = C(G')$

$C(G)$ denotes the cycle set of $G$ (the set of lengths of all cycles of $G$). This question came up recently and I have been meaning to take a stab at it, but I wanted to know if there exists some ...
  • 151
4 votes
1 answer
59 views

Suppose $G$ is a bipartite planar graph such that for any two vertices $A$ and $B$

Suppose $G$ is a bipartite planar graph such that for any two vertices $A$ and $B$, the number of shortest paths from $A$ to $B$ is odd. Prove that $G$ is a tree. Suppose $G$ is a bipartite planar ...
  • 199
2 votes
1 answer
18 views

Can we algorithmically map a Delaunay tesselation in $\mathbb{R}^n$ to a planar embedding in $\mathbb{R}^2$?

Preamble Suppose I have a finite collection of points in $\mathbb{R}^n$, and I compute a Delaunay tesselation on them. In this $n$-dimensional space the straight-line edges are non-intersecting line ...
  • 1,559
2 votes
1 answer
38 views

Do minimum spanning trees drawn on points in $\mathbb{R}^2$ always have non-intersecting edges?

Preamble This question is motivated by the question "Embedded minimum spanning trees for visualizing effects of dimensionality reduction?". Suppose I were to begin with a collection of ...
  • 1,559

1
2 3 4 5
19