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
0 votes
0 answers
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 ...
user avatar
  • 335
4 votes
1 answer
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 ...
user avatar
  • 743
3 votes
1 answer
58 views

Conjecture about chordal graphs

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 ...
user avatar
5 votes
2 answers
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 ...
user avatar
  • 61
0 votes
1 answer
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). -&...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 41
4 votes
1 answer
98 views

Fast algorithm to embed a triangulation into plane

Let $G = (V, E)$ be a planar graph such that $|E| = 3|V| - 6$ (so $G$ must be a triangulation without Kuratowski subgraphs). Given the adjacent matrix $A$ of $G$, please design an algorithm to embed $...
user avatar
-1 votes
0 answers
121 views

Partitioning vertex set of a planar graph into two induced outerplanar graphs

I am interested in showing that: For a vertex set of any planar graph, the vertex set can be partitioned into sets $X$ and $Y$ such that the graphs induced by both $X$ and $Y$ are outerplanar. $\...
user avatar
  • 571
1 vote
0 answers
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}$ ...
user avatar
0 votes
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 958
2 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 3
1 vote
0 answers
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 ...
user avatar
  • 743
5 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 571
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
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?...
user avatar
  • 38.5k
1 vote
1 answer
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 41
0 votes
0 answers
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?
user avatar
0 votes
1 answer
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 ...
user avatar
  • 743
2 votes
1 answer
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 ...
user avatar
  • 23
0 votes
0 answers
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 ...
user avatar
  • 396
1 vote
1 answer
38 views

4-cycle addition converts a quadrangulation graph with 2-connectivity into a 3-connected quadrangulation .

Let $H$ be a quadrangulation on the sphere and let $f$ be a face of $H$ bounded by a $4$-cycle $∂f = v_1v_2v_3v_4$. A $4$-cycle addition to $f$ is to put a 4-cycle $u_1u_2u_3u_4$ inside $f$ and join $...
user avatar
  • 743
1 vote
0 answers
29 views

Is there a name for the triangulation which minimizes the sum of the longest edge for each triangle?

Consider a point set $P\subset \mathbb{R}^2$. Let $T$ be a triangulation of $P$. For $t\in T$ a triangle, define $l(t)$ as the length of the longest side of the triangle. I want to find a ...
user avatar
  • 11
2 votes
1 answer
47 views

Reaching the grid graph from a planar graph using graph transformations

Consider a $5$-regular undirected planar graph with $n$ vertices (a $k$-regular graph has exactly $k$ edges emanating from every node.) Let us say we apply an arbitrary sequence (of length $\text{poly}...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 743
8 votes
0 answers
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 ...
user avatar
  • 903
1 vote
0 answers
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 (...
user avatar
1 vote
0 answers
32 views

Toroidal graphs have chromatic number at most $7$

I'm trying to prove that if $G$ is a toroidal graphs, then $\chi(G) \leq 7$. I embedded $K_7$ in the torus and thus there exists a toroidal graph with chromatic number at least $7$, and I showed that $...
user avatar
10 votes
1 answer
516 views

Why is this proof for the four color theorem considered wrong?

I'd like to think I found a proof for the four color theorem, but I also know that it took far smarter people than me a computer simulation to prove. Still, I don't see why this logic should be flawed....
user avatar
  • 227
0 votes
0 answers
51 views

A simple bipartite planar graph having no cycle of length shorter than $5$ satisfies $|E| \le \dfrac{3}{2} |V| -3.$ [duplicate]

Let $G = (V,E)$ be a simple bipartite planar graph having no cycle of length shorter than $5$ then it satisfy the following relation: $$|E| \le \dfrac{3}{2} |V| -3$$ The observations I have done: ...
user avatar
  • 11.9k
1 vote
1 answer
89 views

Prove Herschel graph is nonhamiltonian

Let us denote by $c(G)$ the number of components of graph $G$. Theory: For a hamiltonain graph we have $c(G-S)\leq|S|$ for any set $S$ of vertices of $G$. How can I show that Herschel graph is ...
user avatar
1 vote
1 answer
36 views

joining an even number of odd faces turns out to be an even face?

As I wrote in the title, my question is: Is the resultant face of joining an even number of odd faces an even face? For instance, we can see that the statement is true for the following graph: we ...
user avatar
2 votes
1 answer
64 views

Planar graph with circuit bounding outer face of length $(n-5)/2$ is 4-colorable

I am struggling with an exercise. I am asked to prove the following: Let $G$ be a simple and undirected graph with a fixed planar embedding such that the circuit bounding the outer face has length at ...
user avatar
  • 155
1 vote
2 answers
79 views

Find the $\angle FPA$ in the figure below

For reference: Starting from a point $P$, outside a circle the tangent $PA$ and the secant $PQL$ are drawn. Then join $L$ with the midpoint $M$ of $PA$. LM intersects at F the circle. Calculate $\...
user avatar
  • 4,049
0 votes
1 answer
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 ...
user avatar
  • 1,281
3 votes
1 answer
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 ...
user avatar
  • 1,127
1 vote
1 answer
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 ...
user avatar
  • 1,597
3 votes
2 answers
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 ...
user avatar
0 votes
2 answers
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 ...
user avatar
  • 351
2 votes
0 answers
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!) ...
user avatar
  • 1,127
0 votes
0 answers
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" ...
user avatar
1 vote
1 answer
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 ...
user avatar
5 votes
0 answers
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
  • 105
1 vote
1 answer
56 views

How can these graphs be plannar? Is there a good way to prove it?

I don't know how could I prove these graphs are plannar or not, the book does not give examples how to do so and i'm consufed. Can someone show me how to do it? I'd appreciate
user avatar
0 votes
0 answers
55 views

optimization on graph edges selection

I have the below problem. I wonder if there exists a similar known class of problems (e.g., in optimization, graph theory) which I can relate my problem to, and find a similar solution there. I am ...
user avatar
  • 21

1
2 3 4 5
18