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

872 questions
Filter by
Sorted by
Tagged with
29 views

### Add an edge to a planar graph and preserving planarity

I’m not sure this is the correct StackExchange section. Let me know if I have to change I’m wondering if, given a planar graph $G$ And two vertices $v,u$, is there an efficient algorithm to know if ...
• 335
99 views

### How to prove that there is no planar graph on $13$-vertices with minimum degree $5$?

We know that Euler's formula produces the following result. If $G$ is a planar graph with minimum degree $5$, then it has at least $12$ vertices. I find that the planar graph $H$ on $13$ vertices ...
• 743
58 views

I came up with the following conjecture: Let $G$ be a planar, biconnected chordal graph. Then there always exists a pair of adjacent vertices that have the same degree. Can someone find a counter ...
112 views

### How can I prove that there is not a 5-regular planar graph with 14 vertices.

I tried several approaches, but I cannot prove that such graph doesn't exists. Any hints? The question How many nodes are there in a $5$-regular planar graph with diameter $2$? is related, but the ...
• 61
47 views

### What is a convex combination of graphs?

For example in this paper, they refer to a "convex combination of trees" (pg. 2, first paragraph), and also, more generally, to "convex combination of graphs" (pg. 2, footnote). -&...
30 views

### How to find the number of truly (no simple swapping of colors) distinct vertex colorings of a graph?

I am a layman when it comes to mathematics, computer science and , thus, also graph theory. But for designing a psychological experiment based on simple graphs I need to know how to find the number of ...
• 41
98 views

• 571
1 vote
14 views

### Find crossing edges in a graph from adjacency matrix

Is there any way to find the crossing edges from the adjacency matrix of a given undirected graph $G=(V,E)$? For example in the following graph ( actually a tree in this specific example) $e_{3, 13}$ ...
• 111
27 views

### Example of a locally finite graph without a uniform degree bound

We call an infinite graph locally finite if every vertex of it is of finite degree. A locally finite graph is said to have a uniform degree bound if the degree of every vertex of it is bounded by some ...
1 vote
19 views

### Prove that an edge in planar graph cannot belong to three faces using the Jordan curve theorem

Given a planar drawing $D$ of a graph $G$, how can I prove that an edge cannot belong to three faces in the drawing $D$? I am looking for a proof that uses the Jordan curve theorem, and does not ...
• 958
29 views

### Can the Petersen graph be embedded into the 3-dimensional Euclidean space such that every edge has unit length?

By embedding I mean that its edges may intersect only at their endpoints. The precise definition can be found here. We know that the Petersen graph can be drawn in the plane such that every edge has ...
• 771
1 vote
26 views

### Placing $n$ vertices in the plane such that no 3 edges cross the same point

Problem I would like to embed a graph containing $n$ vertices in the plane. Is there a systematic way to assign coordinates such that no matter what edges the graph contains, no three edges will cross ...
68 views

### Does there exist a graph embedding that fulfils Euler's formula and is not planar?

Let $G=(V, E)$ be a connected graph such that $r=m−n+2$, where $r$ is the number of regions, $m$ is the number of edges and $n$ is the number of vertices. Does there exist a graph embedding of a ...
• 3
1 vote
26 views

### The upper bound on the number of four cycles of 3-connected quadrangulation graphs.

Recently I was thinking about a question: what is the upper bound on the number of four cycles for 3-connected quadrangulation graphs with $n$ vertices? I use the plantri software, and propose the ...
• 743
98 views

### How to draw a planar-embedded graph in a visually pleasing way

I have a graph with two types of vertices: "boundary" vertices have degree 1, and "interior" vertices have degree 4. I've computed a planar embedding of the graph, i.e. around each ...
• 9,047
1 vote
24 views

### Partitioning vertex set of Outerplanar Graph

I am able to use induction method to partition the vertex set of any outerplanar graph into two sets say $X$ and $Y$ such that the two sets induce forests with maximum degree at most 2. I was ...
• 571
1 vote
39 views

### Subgraph embedded

Suppose I have a planar graph (without loops, vertices of degree one or multiple edges) such that each face (including external) has six edges and there ther ore no two adjacent vertices with degree ...
26 views

### Can a planar graph with a 3-cycle always be drawn with a 3-sided face?

In general a planar graph can be drawn in many different ways. Can a planar graph that has a cycle of length three nevertheless not have any planar representation which includes a face of degree three?...
• 38.5k
1 vote
62 views

### Degree of vertices in a planar graph.

Suppose I have a planar graph (without loops or multiple edges) with $3n$ edges such that it has $n$ faces and each face (including external) has six edges. Is it true that either: there exists two ...
45 views

### How to construct a graph with six vertices that has the chromatic number 4 (not 3)?

I have a question related to graph theory. First, I want to state that I am not a mathematician or computer scientist, but a psychologist doing research on cognitive processing related to computer ...
• 41
16 views

### What is the Dual Planar Graph of 1 vertex with 0 edge?

I learned Dual Planar Graph today, and I take it as a representation of the edge-sharing diagram. Then I start thinking what is the dual planar graph of 1 vertex with 0 edge?
40 views

### Can vertex connectivity of a plane graph be characterized by a special closed Jordan curve?

Let $P$ be a plane, and a simple closed curve $l$ on $P$ is separating if $P-l$ is not connected. My question is as follows. Question Let $G$ be a planar graph with connectivity $k$, and $\phi(G)$ be ...
• 743
47 views

### Recursively generate 3-regular planar graphs

I'm trying to prove that there are an unbounded number of (non-isomorphic) 3-regular planar graphs with faces of degree 3 or 6. I know that there are only 4 faces of degree 3 in such a graph. I cannot ...
• 23
28 views

### Graph that can be drawn to scale

What do you call a weighted graph that you can draw to scale so that every edge is the length of its weight? I understand in just 2 dimensions one of the conditions is that the graph is planar but I ...
• 396
1 vote
38 views

62 views

### Can any planar graph be extended into a bipartite planar graph by a series of operations?

The edge subdivision operation for an edge $\{u,v\}∈E$ is the deletion of $\{u,v\}$ from $G$ and the addition of two edges $\{u,w\}$ and $\{w,v\}$ along with the new vertex $w$. My first question is ...
• 743
90 views

### On a lemma for planar graphs

Throughout, let $G$ be a planar graph with $n$ vertices, $e$ edges and $f$ faces. Additionally, let $n_k$ be the number of vertices of degree $k$ and $f_k$ be the number of faces with $k$ edges. I ...
• 903
1 vote
73 views

### Showing genus of a Petersen graph is equal to 1

In relation to the question asked here Genus of Petersen graph could a possible solution be to construct a rectangle which represents an embedding on a torus where the opposite edges are identified (...
1 vote
32 views

• 4,049
40 views

### If the regions of $H$ can be properly colored using at most four colors, then the edges of $H$ can be properly colored using at most three colors.

Let $H$ be three regular and planar. If the regions of $H$ can be properly colored using at most four colors, then the edges of $H$ can be properly colored using at most three colors. I'm not sure how ...
• 1,281
52 views

### Is there a graph without a $K_5$ subdivision that has a chromatic number of $5$?

The Four Color Theorem states that a planar graph requires at most four colors to be proper colored. The Kuratowski's Theorem states that a graph is planar if, and only if, it doesn't have a subgraph ...
• 1,127
1 vote
94 views

### Maximum number of edges in a balanced graph with n points, without small cycles (say, of length 2, 3, 4)

Let's say we have $n$ points numbered from $1$ to $n$. What is the maximum number of directed edges possible on a graph with these $n$ points: without any cycle of length $\leq k$, for example ...
• 1,597
151 views

### If integration represents the area under a curve, why indefinite integrals gives a function.

Maybe it's a really basic question as i just started learning calculus but If integration represents the area under a curve, why indefinite integrals gives a function as area and how it is related to ...
80 views

### Are all even graphs planar?

Recall that a graph is even when all its vertices are of even degree (number of incident edges; loops contributing two degrees each). If not, is there any extra (set of) condition(s) needed to make an ...
• 351
56 views

### Prove that $2V - 4 = F$ for maximal planar graphs.

A beautiful proof of the Euler's characteristic of planar graphs goes as follows: Let $G$ be a connected planar graph and $\chi(G):=V-E+F$. Add as much edges as possible to $G$ (but no vertices!) ...
• 1,127
27 views

### Proposition of fast algorithm for graph with weights

If ever your Djkstra algorithms are in a situation where the max weight is much smaller than the number of vertices in your graph, try transforming each weight of size "x" into "x" ...
1 vote
58 views

### A question regarding Graph embedding in plane

I am new to Algebraic Topology. So, I would like to have a detailed proof of this following problem as there are many similar and corollary problems in the book that I am reading. Suppose we are given ...
140 views

### Can identical rings intersect in any combinations in 3d space?

For every undirected graph G, with nodes $a_1,...,a_n$. Can we find n circles/rings of fixed radius, $c_1,...,c_n$ in 3 dimensions such that there exists an edge between $a_i$ and $a_j$ if and only if ...
41 views

### Outer faces in disconnected planar graph

Consider a planar graph consisting of two components. Assume that each component is a triangle. We have two faces that are to the left of the edges in each cycle if we consider traversing the cycle in ...
• 105
1 vote