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
1answer
18 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
52 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
38 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
30 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
54 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
19 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
29 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
24 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
32 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
21 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 ...
0
votes
0answers
13 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
34 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
15 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}$?
0
votes
0answers
25 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
32 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
27 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
45 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...
0
votes
0answers
35 views

A plane triangulation is 3-connected: Proof

I want to prove: "A plane triangulation $G$ with at least 4 vertices is 3-connected" I have found this proof. I don't like it but I took some ideas out of it: ...
1
vote
0answers
12 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
19 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
21 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
44 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
11 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
26 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
45 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
139 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
61 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
30 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
14 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 ...
1
vote
0answers
24 views

What is the smallest $5$-vertex-connected ($5$-edge-connected) planar graph?

A planar graph cannot be $6$-connected because the number of edges of a planar graph with $n$ vertices is at most $3n-6$, while a $6$-connected graph with $n$ vertices must have at least $3n$ edges. ...
2
votes
1answer
39 views

Is there a $4$-regular planar self-complementary graph with $9$ vertices and $18$ edges?

Recently, a user asked for the construction of regular self-complementary graphs. I found the graph consisting of the hamilton-circles $$1-5-8-3-9-6-2-4-7-1$$ and $$1-3-5-2-9-4-8-7-6-1$$ with ...
0
votes
0answers
89 views

Proof that a planar graph is eulerian if and only if the dual graph is bipartite

I need the proof that a planar graph is eulerian(a graph that has eulerian tour) if and only if the dual graph is bipartite. Can someone help?
0
votes
1answer
122 views

3-regular connected planar graph

Let $G$ be a 3-regular connected planar graph with a planar embedding where each face has degree either 4 or 6 and each vertex is incident with exactly one face of degree 4. Determine the number of ...
2
votes
0answers
41 views

Graph planarity and electronic circuit boards

In another MSE question, I found the following definition for 2-layer circuit board decomposition of a graph: A circuit board is defined as a pair of planar graphs with vertices identified, i.e. ...
0
votes
1answer
62 views

How would I find the scale factor of a dilated figure on a coordinate plane?

The above question is pretty simple, and I used common sense to figure out that the coordinates (3, -7) is the answer, since it is the only viable spot. I was wondering how I would find the scale ...
1
vote
1answer
114 views

3-regular planar graph

Yet another question I was going over and struggled. Given a 3-regular connected planar graph, so that every vertex lies on the edge of a face of length 4, of a face of length 6 and of a face of ...
-1
votes
1answer
28 views

Trouble determining planarity of graph

I am practicing for an exam and I can not wrap my head around this exercise. I am supposed to show if the given graph is planar by drawing it or show the subgraph that is homeopathic to K 3,3 or K5. ...
1
vote
1answer
30 views

Determining if a graph is planar and if so draw or disprove with Kuratowski's Theorem

This is a practice exercise for in my text that even my professor was having trouble explaining to me. The instructions are in the title. Here is an image of the graph: I believe this graph is not ...
0
votes
0answers
42 views

A planar graph has either 2 faces or 2 vertices of degree less than 3

Practicing for an upcoming test, I stumbled upon this question: A planar graph with at least three vertices has either 2 faces of length at most 3, or 2 vertices of degree at most 3. Which is a ...
0
votes
1answer
84 views

Proof for binary tree is a planar graph

Suppose G is a binary tree. Is G necessarily planar? Give a proof, or a counterexample. My guess is that it is indeed planar but I am struggling to find a formal proof for this. EDIT: Is there a ...
1
vote
1answer
34 views

Number of maximal planar subgraphs

Suppose we have an undirected graph $G$ which is maximal planar, i.e. adding an edge results in $G$ not being planar anymore. How many subgraphs $G'$ does $G$ have such that $G'$ is also maximal ...
8
votes
2answers
238 views

Visual illustrations of circle packing theorem?

Circle packing theorem states: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G. Paper Collins, Stephenson: A circle ...
1
vote
1answer
90 views

Graph Theory Question On Exam Involving colorability of certain planar graph

I had a question on my exam and answered it using what I believe to be an Exhaustive Proof. The teacher marked it wrong, and while I understand there is a simple answer to the question, I would like ...
0
votes
0answers
109 views

Thickness of G when G is a simple connected graph

The thickness of a simple graph G is the smallest number of planar subgraphs of G that have G as their union. Show that if G is a connected simple graph with v vertices and e edges, where v ≥ 3, then ...
1
vote
2answers
525 views

Show that planar graph has at least 4 nodes of degree 5 of less

I am having a problem with this assignment. So the task says: ...
0
votes
3answers
58 views

Planar Graph max min edges

Consider a planar graph with 5 vertices, what is the minimum and the maximum number of edges such a graph can have? The graph need not be connected and is simple.
2
votes
1answer
258 views

Spanning trees in planar dual graph

The amount of spanning trees in a planar graph G is equal to the amount of spanning trees in the dual graph G*. I would like to proove this, i know it's true, but i would like to show that it holds ...
1
vote
0answers
21 views

Planes help please

So I was doing this set of questions: I've done all the questions up to f, but I'm stuck on that. Here's what the mark scheme says, including relevant information needed to do the question So ...
10
votes
1answer
141 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
0
votes
1answer
56 views

Determining Planar Graphs

Take a hexagon and add the three longest diagonals. IS the graph obtained this way planar? I'm able to draw the graph very easily. But I don't really understand how to determine what graphs are ...