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
-1 votes
0 answers
28 views

Determine whether the given pair of graphs are isomorphic:

Determine whether the given pair of graphs are isomorphic:
  • 11
2 votes
1 answer
68 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,180
0 votes
1 answer
39 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
61 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 ...
  • 553
4 votes
1 answer
66 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 $...
  • 24
0 votes
0 answers
16 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
38 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
0 votes
1 answer
47 views

Confused about the proof for a theorem in graph theory

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 ...
  • 142
-1 votes
1 answer
22 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 ...
  • 149
2 votes
0 answers
18 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 ...
  • 916
1 vote
1 answer
56 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
12 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 ...
0 votes
1 answer
17 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
62 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,180
2 votes
1 answer
39 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
41 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 ...
1 vote
0 answers
34 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 ...
  • 13
2 votes
0 answers
53 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 ...
  • 278
0 votes
1 answer
31 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
68 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 ...
  • 278
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/...
2 votes
0 answers
87 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,180
1 vote
1 answer
37 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
58 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
33 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 ...
  • 103
1 vote
1 answer
43 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,180
0 votes
1 answer
50 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
62 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 $\...
  • 10k
3 votes
1 answer
74 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
73 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
71 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
54 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
56 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 ...
  • 109
2 votes
1 answer
16 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,519
2 votes
1 answer
37 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,519
3 votes
0 answers
50 views

Is there a name for this construction of plane graphs?

Let $G$ be a plane graph. Let $G'$ be a supergraph of $G$ obtained by inserting a face vertex in each face of $G$ and connecting the face vertex to all vertices on the boundary of the face. For ...
  • 1,180
1 vote
0 answers
40 views

Prove a graph is not planar

Let $ G = \left(V, E\right) $ be a simple path such that $ \left|V\right| = 10 $. Let $ x, y $ be the leaves of $ G $. Two new nodes, $ v, w $, were added to $ V $ such that there is an edge between $ ...
  • 611
0 votes
1 answer
59 views

Prove $\overline{G} $ is not a planar graph

Let $ T = \left(V, E\right) $ be a tree such that $ \left|V\left(T\right)\right| = 8 $. After adding $ 2 $ edges to $ T $, a simple graph $ G = \left(V^{'}, E^{'}\right) $. I need to show that $ \...
  • 611
2 votes
1 answer
96 views

For any planar quadrangulation $G$, is there a planar drawing of $G$ such that all faces are convex (or non-convex, resp.)?

A simple planar graph $G$ is called a quadrangulation graph if $G$ has a planar drawing in which all faces are quadrangular faces. A polygon is convex if all the interior angles are at most 180 ...
  • 1,180
2 votes
1 answer
69 views

Does a triangulation $T$ such that $\kappa(T)=3$, $\kappa'(T)=4$ and $\delta(T)=5$ exist?

Some terminology and notation: A simple plane graph in which all faces are triangular faces is called a triangulation. The vertex connectivity of a graph $G$, written as $\kappa(G)$, is the smallest ...
  • 1,180
0 votes
1 answer
103 views

A question about the four-color problem

I remember there was a theorem in the history, concerning the four-color problem. It states something like following: in a map, the maximal number of regions that can be neighbors to each other is 4. ...
  • 123
0 votes
1 answer
84 views

Homology group of a planar graph

In my Algebraic Topology course we are studying topological and there is some point in a proof I am struggling with. We define a graph $(G, V)$ such that $V \subset G$ is finite, $G\backslash V$ ...
  • 3,162
0 votes
0 answers
52 views

How high the connectivity of a planar graph can ensure that any two faces share at most two vertices?

Once I asked the following question. Question 1 (solved): Do any two faces share with at most one edge in a 3-connected plane graph? Do two faces of any 3-connected planar graph have at most one ...
  • 1,180
1 vote
1 answer
33 views

Comparing network graphs

I started out with a grid graph, performed some operations on it, and ended up with a set of networks; for example, , , , I need to compare these graphs. A thought that I had was to compare them with ...
  • 278
3 votes
1 answer
177 views

If $\Delta(G)≤3$, then planarity of $G$ implies planarity of the line graph $L(G)$.

This appears that a similar version of my question has been discussed on stack. Nevertheless, I have yet to see a rigorous proof. General planar graph L(G) So I presented it again. Claim: If $G$ is ...
  • 1,180
0 votes
0 answers
33 views

Comparing networks using graph theory

I'm new to graph theory so forgive if I use unconventional terminology. Please ask if there's any confusion regarding the statements I make. I have a bunch of undirected, unweighted, simple graphs ...
  • 278
1 vote
0 answers
43 views

graph theory - maximal graph without cycles and maximal planar graph without triangles

Let there be $G = (V,E_1\cup E_2)$ such that $(V,E_1)$ is a planar graph without triangles, and $(V,E_2)$ is without circles, show that $G$ is $6$-colorable Can I prove here that $E_1$ and $E_2$ has ...
3 votes
1 answer
72 views

How many planar graphs of vertex degrees all ≥4 are there?, extended (by request of G.M.)

An extension to this. How many planar graphs of vertex degrees all ≥4 are there? Now that I have seen infinite cases (from VTand's answer), is there any way to describe all of them? i.e. Does all ...
4 votes
1 answer
75 views

How many planar graphs of vertex degrees all $\ge4$ are there?

How many planar graphs that satisfies $\forall\ v\in V\deg(v)\ge4$ are there? If there are finite numbers, can you list them/link them? If there are infinite, is there a proof? I assume there are ...

1
2 3 4 5
19