A planar graph is a graph (in the combinatorial sense) that can be embedded in a plane. In other words, there is some pictorial representation of the graph such that the edges only intersect at vertices. Consider tagging with (combinatorics) and (graph-theory).

learn more… | top users | synonyms

1
vote
0answers
19 views

Analogue of Fáry's theorem taking sphere and geodesics instead of plane and straight lines.

Fary's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments (see Wikipedia). The proof is based on the Art gallery theorem, so I ...
2
votes
1answer
24 views

Dual graph of a tree

It is stated here that: For any connected embedded planar graph G define the dual graph G* by drawing a vertex in the middle of each face of G, and connecting the vertices from two adjacent ...
2
votes
2answers
41 views

Give a formal argument why there is no planar graph with ten edges and seven regions. Here is my answer

I'm really new to a graph theory, and I have to answer the following question: give a formal argument why there is no planar graph with ten edges and seven regions. Here is my answer: Using ...
0
votes
0answers
11 views

Orthocenter of triangle given by vectors in $3$-dimensional space [closed]

Given: $B=(1,0,0), D=(0,1,0), E=(0,0,1)$. Question: find the coordinates of the orthocenter $L$ around triangle $BDE$. With the formula used
1
vote
1answer
29 views

Approach to determining if a graph is planar by inspection/kuratowski's theorem

I'm taking an intro discrete math course and am having trouble determining if a graph is planar or not. When proving a graph is planar, if Euler's formula doesn't apply I just randomly redraw the ...
0
votes
0answers
18 views

Can someone advice edge contraction tool?

I need to show how edge contraction happening in graphs and the best way for it is visual presentation. Maybe someone can give an advice about a tool where it can be simply represented. Maybe a ...
0
votes
0answers
17 views

Left-Right planarity Testing for Petersen graph

Could somebody tell me how to use the signed constraint of the left-right planarity criterion to show Petersen graph is not planar?
0
votes
0answers
21 views

An example of a DFS-oriented graph

Could somebody give an example of a DFS-oriented graph with a non-aligned LR-partition such that the corresponding LR-ordering does not yield a planar embedding?
0
votes
1answer
44 views

What is a graph that contains subdivision but not minors and vice versa?

I am looking for graphs which satisfy the following conditions. (I have tried finding some possible solutions but no way to confirm them) (a). a K5 as a minor but no K5-subdivision? ans. Petersen ...
0
votes
1answer
28 views

An example for a planar graph with different embeddings with different degree sequences of the faces?

Let $G$ be a planar graph with a planar embedding with $f$ faces. The degree of a face $f_i$ is the number $a_i$ of edges that are incident to $f_i$ (counting bridges twice). Assume that the faces ...
3
votes
2answers
60 views

Crossing of strings

There are two strings of color red and blue. They are made to cross each other odd number of times (greater than one) without any self crossing. Is it always possible that there will be pair of ...
1
vote
3answers
60 views

$K_{3,3}$ an exception to Planar Graph formula

So I have learned that for a graph to be considered Planar, if it has at least 3 vertices, you can apply the following formula to test for planarity: number of edges ≤ 3(number of vertices) - 6 also ...
0
votes
1answer
40 views

Prove: If $G$ is a planar graph with $p$ vertices, $q$ edges, and finite girth $g$ then, $q \leq \frac{g(p−2)}{g−2}$ .

Prove the following theorem: If $G$ is a planar graph with $p$ vertices, $q$ edges, and finite girth $g$ then, $$q \leq \frac{g(p−2)}{g−2}$$ . I do not know how to go about proving this, besides the ...
0
votes
1answer
31 views

What is the maximum number of edges you can add to the wheel Wn and still obtain a planar graph?

What is the maximum number of edges you can add to the wheel Wn and still obtain a planar graph? I know that the outside of the wheel can always be a cycle of 3 and that W4 has max edges=6, W5=9, ...
1
vote
1answer
47 views

Graph theory question(about planar graphs, degrees)

Prove, that every planar graph, which has no loops or multiple edges, and has more than 3 vertices(it can be 3 too), has at least 3 vertices, which have 5 or less degree. I kinda can't start this, I ...
1
vote
3answers
169 views

Every planar graph can be embedded on a sphere - formal proof?

The proof of the following theorem: A graph can be embedded on the surface of a sphere without crossings if and only if it can be embedded in the plane without crossings. is very short- The ...
3
votes
1answer
81 views

Every polyhedral graph is planar - proof

Every graph theory book or internet resource on graph theory says the graph of a convex polyhedron is planar, i.e. it can be drawn on a plane without edges crossing. Graph of a convex polyhedron is ...
-1
votes
1answer
20 views

Prove concerning planar graph

I need to prove that in a planar graph with more than two vertexes at least a vertex with a maximum grade of five exists. I know that planar graphs fulfill the relation $\#E \le 3\#V-6$, and relation ...
6
votes
2answers
462 views

Is there a planar graph that (almost) all its vertices have degree 6?

Is it true that for any $N_0\in\mathbb N$ there exists a planar graph $G=(V,E)$ on (at least) $N_0$ vertices such that at least $$|V|(1-o(1))$$ vertices has degree 6? It is easy to show that no ...
1
vote
1answer
29 views

If edges of $G$ are two colored, then there is a vertex of $G$ with at most two col0or changes in the cyclic order of the edges around the vertex.

Hello there i am reading proofs from the book of Gunter M ziegler. The chapter is called Three applications of eulers formula. Know there is a proposition which i don't fully understand and help would ...
1
vote
1answer
33 views

Find Planar Graph fromVertices and Faces

Could you find a 3-Regular Connected Planar Graph on 10 vertices with 8 faces? If so, explain carefully. I dont know what does regular mean. I think that 3-connected graph on 10 vertices with 8 ...
2
votes
1answer
87 views

Graph theory question about planar graphs

How can i prove that every planar graph can be expressed as a union of five edge-disjoint forests ? I think I should use theorem that says : ' Every planar graph contains vertex with degree 5 or ...
1
vote
1answer
36 views

Triangles formed by line segments in a square

There is a square, denoted by points A, B, C, and D. There are 30 distinct points located inside the square (call these $A_2, A_3, A_4, ... A_{31}$. Non-intersecting segments $A_iA_j$ vertices are ...
4
votes
1answer
90 views

Every simple planar graph with $\delta\geq 3$ has an adjacent pair with $deg(u)+deg(v)\leq 13$

Claim: Every simple planar graph with minimum degree at least three has an edge $uv$ such that $deg(u) + deg(v)\leq 13$. Furthermore, there exists an example showing that 13 cannot be replaced by ...
1
vote
1answer
47 views

Proving the upper bound of edges in a convex polyhedron

The question is the following: Suppose Every face of a convex polyhedron has at least $5$ vertices and every vertex has degree $3$. Prove that if the number of vertices is $n$, then the number of ...
0
votes
2answers
36 views

Can anyone give an example for this theorem related to planar graphs?

Theorem: Let $G$ be a connected planar graph with $p$ vertices and $q$ edges, where $p\geq 3$. Then $q\leq3p-6$. Proof: Let $r$ be the number of regions in a planar representation of $G$. By ...
7
votes
1answer
73 views

Can a planar graph be drawn with all vertices on a straight line?

I have been repeatedly trying to prove and disprove the following: Can any planar graph, with $n$ vertices, be drawn such that the vertices are fixed at coordinates $(0,0)$, $(1,0)$, ..., ...
0
votes
0answers
20 views

Bridges at a non planar graph

Is there any algorithm that gives us the minimum number of bridges we will have to use if a graph is not planar?
0
votes
0answers
33 views

Why is it not possible to draw the $\overline{Q_3}$ in the plane

I am trying to prove that $\overline{Q_3}$ is nonplanar. I know that $Q_3$ is planar and I have attempted to use the corollaries derived from Euler's planarity Theorem to show it is nonplanar but it ...
0
votes
1answer
28 views

Planar graph with V ≥ 2 has at least 2 vertices whose degrees are at most 5

If G was a planar graph on V ≥ 2 vertices. How would I go about proving that G has at least 2 vertices whose degrees are at most 5? I understand that planar graphs can be drawn so that every edge is ...
0
votes
1answer
40 views

Proving if planarity puzzle is planar

An "untangle" game app I have has scrambled planar graphs to be organized by dragging the nodes around until no lines cross. When solved, the puzzle is a lot of triangles. Some nodes have only 2 or 3 ...
1
vote
1answer
50 views

Partitioning a planar graph into spanning trees?

Suppose I have a simple, planar graph, which I want to partition into three edge sets such that each set forms a spanning tree. I've made an attempt at a solution, but it requires a few assumptions ...
-1
votes
0answers
16 views

Prove: if G has exactly one $C$-fragment, then there exists a cycle $C$ in a 3-connected graph that is the boundary of a face in $G$.

If G has exactly one $C$-fragment, then there exists a cycle $C$ in a 3-connected graph that is the boundary of a face in $G$. If there is a cycle, then it has to be the boundary of a face (right?). ...
1
vote
2answers
47 views

Edge contraction and subdivision

Let $G$ be a $3$-connected graph that is not homeomorphic to $K_5$ or $K_{3, 3}$. Let $G'$ be the graph obtained from $G$ by contracting an edge. Why is it the case that $G'$ contains no ...
0
votes
0answers
18 views

Why does adding a vertex $x$ that is adjacent every vertex in $G$ with a subdivision in $K_{3,3}$ or $K_5$ result in subdivison of $K_5$ or $K_{3,3}$

Why does adding a vertex $x$ that is adjacent every vertex in a subdivision in $K_{2,3}$ or $K_4$ result in a graph that is a subdivision of $K_5$ or $K_{3,3}$?
-1
votes
0answers
55 views

How many edges must you remove from Peterson graph to make it planar

The answer is 2. Why is it not 1? Context: I understand that the Peterson graph is not planar (b/c it contains $K_{3,3}$). What I don't understand is why 1 removing 1 edge doesn't do the job. I've ...
0
votes
1answer
36 views

clarifiying a definition from graph theory more prcisely definition of A-Bridge

I really don't understand this definition from this paper which is: $A-bridge$: if $A \subseteq V(G)$, then an $A-bridge$ of $G$ is either an edge joining two vertices of $A$ or an edge-maximal ...
0
votes
1answer
30 views

G with n vertices is planar if it has most an vertices

“if a connected graph with $n$ vertices has at most $αn$ edges, then $G$ is planar.” For what real numbers $α$ is this statement always true? Prove your answer in both directions. I tried to use ...
1
vote
0answers
50 views

Prove or disprove: If G is bipartite and does not have K3,3 as a topological minor, then G is planar

Prove or disprove: If G is bipartite and does not have K3,3 as a topological minor, then G is planar. I really have no idea how to do this...
1
vote
0answers
14 views

possible embeddings for a $2$-connected planar graph

When I asked the question "cycles and faces in planar graphs", I learned that the numbers of vertices in the faces are not unique, if the planar graph is only $2$-connected. My question now is : How ...
2
votes
0answers
22 views

Does every polyhedral graph have a path cover with non-empty paths?

I'm looking to prove or disprove the following conjecture: Every polyhedral graph has a path cover with vertex disjoint, non-zero (length $\ge 1$) paths. Any pointers to literature are appreciated. ...
0
votes
1answer
23 views

Planarity Criterion

I am looking for a proof of the theorem: If a planar graph, $G$, has $v$ vertices ($v \geq 3$) and no cycles of length 3 then, $e \leq 2v-4$. I remember doing this in a graph theory course and I ...
1
vote
1answer
52 views

Planar graphs and connectivity

How many edges must a planar graph with $n$ nodes have that it is sure that it is a) connected b) biconnected c) triconnected In particular, are all planar graphs with $n$ nodes and $3n-6$ edges ...
0
votes
0answers
12 views

Embeddings of a $2$-connected planar graph

Suppose, I have the adjacency matrix of a $2$-connected planar graph. The embedding might not be unique. How can I find out which embedding (or embeddings) the graph has without drawing it ? The ...
4
votes
0answers
27 views

Is this the smallest graph with the desired properties?

The above graph has the following properties : $1$) Every vertex is start vertex of some hamiltonian path. $2$) It contains no hamiltonian cycle. $3$) It has no cycle of length $3$. $4$) It is ...
1
vote
0answers
46 views

Convex planar graphs

A planar graph is called convex, if it can be drawn in a way such that every face, including the outer face is convex. Wikipedia states that a planar graph is convex if and only if it is a ...
1
vote
1answer
210 views

A space curve is planar if and only if its torsion is everywhere 0

Can someone please explain this proof to me. I know that a circle is planar and has nonzero constant curvature, so this must be an exception, but I am a little lost on the proof. Thanks!
1
vote
1answer
91 views

Cycles and faces in planar graphs

Let G be a connected planar graph. Supopose, we know all cycles of G. Is this enough to determine the length of the face boundaries ? In particular, are the lengths of the face boundaries unique ...
1
vote
0answers
31 views

Which sequences $d_1,\ldots,d_n$ guarantee the planarity of a graph?

Which sequences $$d_1,\ldots,d_n$$ $$d_1\le \cdots\le d_n$$ have the property, that every graph with this degree sequence is planar ? It is clear that every sequence with $d_n\le 2$ works. As for ...
1
vote
0answers
15 views

Which degree sequences $d_1,…,d_n$ are planar-graphical?

Which degree sequences are planar-graphical, that means for which degree sequences $$d_1,...,d_n$$ $$d_1\le...\le d_n$$ exists a PLANAR graph that has this degree sequence ? I found some links in ...