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
2
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
-1
votes
0answers
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$....
-1
votes
0answers
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*. **
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
4
votes
1answer
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$ ...
0
votes
2answers
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?
0
votes
1answer
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?
2
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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)...
-1
votes
1answer
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" ...
3
votes
1answer
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 (...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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$...
0
votes
0answers
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 ...
0
votes
1answer
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?
0
votes
0answers
23 views

planarity of multigraph

Let $G=(V,E,B)$ ($B$ is the incidence function for edges st $B(v,e) = 2$ iff $e\in E$ is a loop, $B(v,e) = 1$ if $v\in e$ and $e$ is not a loop, etc.). Define the simplification of $G, $ denoted $si(G)...
0
votes
1answer
38 views

Intuitive way of constructing a graph with a large chromatic number?

I want to construct a graph with a relatively large chromatic number (10). My only problem is that I can't have K9 (or the complete graph with 9 vertices) as an induced subgraph. Also My edges are at ...
0
votes
1answer
59 views

Let $G$ be a simple planar graph in which every vertex has the same degree $k$. Prove that $k \leq 5$

Let $G$ be a simple planar graph in which every vertex has the same degree $k$. Prove that $k \leq 5$. This is a problem I was given by my professor, but I am struggling to see why it would be true, ...
0
votes
1answer
20 views

Finding $K_{3,3}, K_{5}$ as subgraphs

Hey I am supposed to determine if this graph is planar. I know, that it is not. But I failed to find $K_{3,3}, K_{5}$ as subgraphs. Can anyone help?
2
votes
1answer
29 views

Find a closed formula for the number of regions in a graph

Suppose that the complete graph $K_n$ with $n$ vertices is drawn in the plane so that the vertices of $K_n$ form a convex $n$-gon, each edge is a straight line, and no three edges cross at a point. ...
1
vote
0answers
32 views

Number of unique figures in a grid with $n$ lines drawn without lifting the pen

The problem is to find the number of distinct figures drawn from $n$ straight lines of fixed length in a grid, which I call snakes. Reflections and rotations of the snakes are identified, so the ...
1
vote
1answer
68 views

How to come up with an example of a triangulation with two adjacent vertices of odd degree?

We define a triangulation as a planar graph with all faces(including the outer one) as triangles. What is an example of a triangulation with exactly two vertices of odd degree that are adjacent to ...
0
votes
0answers
20 views

Explanation of proof for planar bipartite graph

I am supposed to prove that a bipartite planar graph has a vertex of degree at most 3. I saw this answer. But I am little bit confused. I do not understand the following part: For planar bipartite ...
0
votes
1answer
38 views

Every maximal outerplanar graph has exactly 2n-3 edges

An outerplanar graph is a graph that can be drawn as a planar graph where every vertex is incident to the outer region. A maximal outerplanar graph can be drawn such that every vertex is part of a ...
0
votes
2answers
28 views

Proof that bipartite planar graph has a vertex of degree at most 3

I'm trying to understand proof that bipartite planar graph has a vertex of degree at most 3. I found this proof: Prove that a bipartite planar graph has a vertex of degree at most 3 . However, I'm not ...
0
votes
1answer
26 views

Vertices of Connected Planar

(a) A connected planar graph $G$ has $20$ faces, and every vertex of $G$ has degree exactly $4$. Find the number of vertices of $G$. (b) A connected planar graph has $26$ faces and $V$ vertices, and ...
-2
votes
2answers
51 views

the number of pairs $(l,p)$ where $p \in P$ and $l \in L$ and that the point $p$ lies on the line $l$ is at most $\sqrt{2}n^{3/2}+n$?

Is it true that for every integer $n$, if one chooses any set $L$ of $n$ distinct lines in the plane and any set $P$ of $n$ distinct points in the plane, then the number of pairs $(l,p)$ where $p \in ...
0
votes
0answers
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 ...
1
vote
1answer
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? ...
2
votes
1answer
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. ...
3
votes
1answer
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*
5
votes
1answer
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 ...
1
vote
1answer
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?
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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?
0
votes
1answer
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/...
0
votes
0answers
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 ...
0
votes
1answer
37 views

Finding an area under the curve with no area

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

How to know if a graph contains subdivisions of $K_{3,3}$ or $K_{5}$

I've been reading about planarity in graph theory and I am kind of a newbie. I know that according to Kuratowski's Theorem (1930) "a graph is planar if and only if it contains no subdivision of $...

1
2 3 4 5
14