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

691 questions
Filter by
Sorted by
Tagged with
30 views

### Algorithm for checking if a given embedding is planar in less than $O(n^2)$ time.

Given an embedding of a graph (with that I mean a concrete spacial layout of the graph on the 2D plane with only $n$ straight edges. Is this the right terminology?), how can I determine if that ...
21 views

### Number of planar triangular $n\times n\times n$ nonnegative integer grids

https://oeis.org/search?q=245+planar&language=english&go=Search I have found this sequence on OEIS. I am trying to understand what is really saying and trying to visualise it but I cannot ...
102 views

### Proving Chromatic Number without 5-Color Theorem

We are currently studying planar graphs and I have come across a review exercise that is proving to be more trouble than it's worth. The problem is as follows: Let G = (V;E) be a planar graph with at ...
30 views

### Weak 2-coloring of a graph but one color is stong?

Given a planar graph how can I color its vertices with 2 colors, A and B, given that: Color A cannot have a neighbor of color A and should have 1 or more neighbors of color B Color B can have any ...
28 views

### Number of faces in Bipartite simple graph

Prove that the number of faces of a simple bipartite graph on 3 vertices is 4 faces? The number of edges in a planar bipartite graph of order $n$ is at most $2n-4$. Proof: Let G be a planar bipartite ...
25 views

### No face with a boundary walk of length more than $3$ is colourful…

Let $G$ be a connected planar graph with a fixed planar embedding. Let $f:V(G)\to1,2,3$. Let us call a face colourful if for each $i\in\{1,2,3\}$, its boundary walk contains a vertex $v$ with $f(v)=i$....
15 views

### Show that the edges forming a spanning tree in a planar graph G correspond to the edges forming a set of chords in the dual G*. [closed]

** Show that the edges forming a spanning tree in a planar graph G correspond to the edges forming a set of chords in the dual G*. **
16 views

### Can a regular triangular grid graph expressed as a transformation of a regular square grid graph?

I was wondering how would I describe a regular triangular grid graph as a transformation of a regular square grid graph? This is the way I thought about it: if I have a grid graph consisting of ...
61 views

### Find a generating function for unlabeled graphs

Let's take a graph(undirected) of $m$ edges and $3$ vertices. Now I want to derive a polynomial for which the coefficient of $x^m$ denotes the number of unlabeled graphs of $m$ edges. How to derive ...
20 views

### Prove that a planar and triangulated graph is k connected if and only if it has no separating cycle of length at most k−1

Let G be a planar graph with a fixed planar drawing $Γ$. A separating cycle of G is a cycle $C$ such that the curve traced by $C$ in $Γ$ has at least one vertex strictly inside and strictly ...
32 views

### How many vertices does a planar graph need to have a complete $k$-colouring?

A proper colouring $V(G) \to \{1,...,k\}$ of a graph $G$ is complete if every distinct pair of colours is connected by an edge. What is the least $n_k$ such that there exists a planar graph on $n_k$ ...
26 views

### What is minimum number of edges should be removed from $K_6$ to get planar graph?

What is minimum number of edges should be removed from $K_6$ to get planar graph? It is easy to show it just with picture.. but is it possible to prove it analytically?
27 views

### Euler's formula for connected, planar graphs.

So I have to prove the graph in the picture is planar using Euler's formula $v - e + f = 2.$ It obviously is planar, but the formula for it is $9 - 12 + 6 = 3$. What am I doing wrong?
36 views

### Can Euler's characteristic formula be proven for maximal planar graphs by double counting?

A maximal planar graph is a planar graph such that adding an edge to it would make it non-planar. It's clear that every face in a maximal planar graph is bounded by exactly three edges. Of course ...
18 views

### Separate overlapping edges in graph

For a given set of nodes in 2d euclidean space and a set of paths over this nodes how can i separate edges from each other in a way that it results in a minimal crossing of edges. Let me make a simple ...
8 views

### For the topic of graph transformations, is there a better way to know which dilations and transformations commute, rather than memorising the facts?

In school we are given a list of the transformations/dilations that do or do not commute and just memorising these isn't very beneficial. How can I know with a deeper understanding (minimal memorising)...
27 views

### Is it true that any 3-regular bipartite graph containing $K_{3,2}$ as subgraph must be non-planar?

I asked a similar question previously at Is it true that any 3-regular graph containing K_{3,2} as subgraph must be non-planar? The requirement can be relaxed so that the $K_{3,2}$ "locally" ...
42 views

### Is Petersen Graph without an edge planar

Let G be the Petersen graph. Is G-e planar? If no, explain why. If G-e is planar, then draw a plane graph isomorphic to it. So we can remove 3 types of edges. 1) Connecting 2 vertices on the outside (...
27 views

### General planar graph $L(G)$

Let $G=(V,E)$ be a graph. Show that if $G$ is planar and $3$-regular then the line-graph $L(G)$ corresponding to $G$ is also planar. Considering small examples might help. I can find an embedding for ...
20 views

### Are there general tips for determining whether a graph is planar or nonplanar? (And, if planar, an approach for finding a planar embedding?)

Are there general tips for determining whether a graph is planar or nonplanar? If a graph is planar, is there a general approach for finding a planar embedding? I usually try to draw out the vertices ...
19 views

### determining whether a graph on $8$ vertices is nonplanar

Determine, with justification, whether the graph $G$ below is nonplanar. I'm not sure whether the graph is planar. I can't really see how to find a planar embedding for it, despite having attempted ...
52 views

### determining whether $H$ is a nonplanar graph

Determine, with justification, whether the graph $H$ below is nonplanar. I think it's nonplanar as I can find a $K_{3,3}$ subdivision for it. I can describe the subdivision as follows. Join vertex $8$...
18 views

### Showing that the faces of the graph $G$ have degree at least $3$

Let $G$ be a simple graph with at least $2$ edges. Prove that every face $F$ of every plane embedding $(\mathcal{P}, \Gamma)$ of $G$ has degree at least three. Let $P := (\mathcal{P}, \Gamma)$ be a ...
18 views

### Prove that planar graph with girth at least 6 contains a vertex of degree at most 2. [closed]

I'm trying to prove that planar graph with girth at least 6 contains a vertex of degree at most 2. However, I'm not sure how would I do so. Could you please help me?
23 views

148 views

### draw a planar connected graph with 81 vertices and maximum degree 4 and diameter 6

I have problem with drawing a planar connected graph with 81 vertices and maximum degree 4 and diameter 6. at first I draw a big plus and tried to put as much vertices as possible on it so that ...
20 views

### Maximum number of edges in a concave polyhedron given n vertices

Given $n$ vertices of a concave polyhedron (3D), what are the maximum amount of edges it can have? I know for convex polyhedra the upper bound is $3n-6$. Does this also hold for concave polyhedra? ...
41 views

### Constructing a planar embedding from rigid vertices.

I have a list of vertices with a cyclic ordering on their edges (rigid vertices). Note on Rigid Vertices I'm not sure how widespread the concept of rigid vertices are, and this helps illustrate them. ...
98 views

### How to check if a graph is biplanar (thickness =2)?

Given a graph G how does one check if it can be decomposed into 2 planar graphs other than enumeration. Note: my given graph has 52 edges and 11 nodes. Quick edit: the graph has an edge from 4 to 1*
158 views

### Two from Cubic Subgraph Hardness

The Problem For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3. The cubic subgraph problem is NP-hard even in bipartite planar graphs with ...
36 views

### Existence of 3-regular connected bipartite planar graphs of order 14

I'm struggling with finding 3-regular, connected bipartite planar graphs on 14 vertices. I tried starting with a cycle on all vertices but I couldn't quite get a planar graph. Can someone help?
24 views

### Euler's Relation for Planar Graphs

In my class, we're looking at this proof that says "By Euler's relation $3v_{3}+2v_{4}+v_{5}=12+\sum_{k\geq7} (k-6)v_{k}$." I know that there are different ways we can rewrite Euler's ...
49 views

### Map colouring algorithm for rectangular regions

We are interested in the class of maps formed of rectangular regions drawn on squared paper (or blocks of cells on a spreadsheet). So the adjacency graph has a natural ordering from the top-left to ...
46 views

### Number of edges in a planar graph where every face has five sides

This was a practice question I saw. I'm kinda confused about the part that says $5f = 2e$. Could someone explain that? Question: What is the number of edges in a planar graph where every face has ...
17 views

### Terminology for A line Pattern that Doesnt Cross

I am looking for terminology to the line pattern that we can draw connecting certain points such that the lines doesnt cross. Is there such a name?
32 views

### Graphs: Recognizing a $P_4$ subgraph

I'm trying to build an algorithm that says if a graph is trivially perfect or not. I realized that I can look if a graph is $(C_4, P_4)$-free as they are equivalent. (https://graphclasses.org/classes/...
24 views

### Determining unknown scalar using area relationship

I have the following equations and trying to determine the value of $a$ $g(x) = ax$ $f(x) = -2(x-3)(x^2+1)$ I am trying to identify the unknown value of a > 0 such that the following holds: the ...
Hello I am trying to explain why the function h(x) $h(x)= x^{99} + x$ will always have the area without determining an antiderivative of h(x) that we must have First I thought of drawing the graph ...