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
8 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
18 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
19 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
38 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
10 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
24 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
43 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
127 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
49 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
29 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
12 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
23 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
33 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
83 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
95 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
36 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
37 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
48 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
23 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
21 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
38 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
54 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
33 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
225 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
80 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
71 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
286 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
52 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
135 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
128 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
39 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 ...
2
votes
2answers
107 views

Proving corollary to Euler's formula by induction

I'm currently looking at two proofs to the following corollary to Euler's formula and I'm not quite seeing how the authors can make a specific assumption in their proof. One proof comes from my ...
1
vote
1answer
71 views

Is a butterfly network on 8-inputs planar?

I could prove that a four input butterfly network is planar. For that I simply drew it such that no two edges intersect. But I could not use the same approach for the 8-input butterfly network. So I ...
0
votes
0answers
75 views

Prove that a certain graph and its dual are 4-colorable

Let $G$ be a simple planar graph with fewer than 12 faces. Suppose that each vertex of $G$ has degree at least $3$. prove that $G$ and its dual are 4-colorable. I'm not too sure how to approach ...
3
votes
1answer
35 views

Forbidden toroidal minors

A finite graph is planar if and only if it does not have $K_5$ or $K_{3,3}$ as a minor. Is there a (finite) set of minors that can classify if a graph is toroidal?
0
votes
2answers
83 views

Planar complete tripartite graphs

For which values of $r$, $s$, and $t$ is the complete tripartite graph $K_{r,s,t}$ planar? Obviously I want to look for either a $K_5$ or a $K_{3,3}$ in order to show that a specific graph is ...
0
votes
1answer
89 views

Five-coloring plane graphs

These days I've been reading about graph coloring. Right now I'm dealing with the five color theorem. I know how to prove that every planar graph is 6 and 5 colorable. I'm looking on the proof of the ...
2
votes
1answer
64 views

Simple planar graph

What's the best way of proving this? ...
0
votes
1answer
122 views

Finding Number of Edges and Vertices in Icosahedron

This is a practice question from a practice test I am working on. ...
0
votes
0answers
18 views

Find and write the proof of an extension of Euler's theorem for a graph…

Find and write the proof of an extension of Euler's theorem for a graph G(V, E) loop-free with number of vertices v, number of edges e, and number of components k. I think the theorem asked is ...
0
votes
1answer
56 views

Suppose G is an unconnected planar graph, with v nodes, e edges, and f faces, where v ≥ 3.

This is a corollary of Euler's formula. I know the proof for connected planar graphs but I have to prove it for unconnected planar graphs. Suppose $G$ is a connected planar graph, with $v$ nodes, ...
0
votes
2answers
69 views

Let G= (V,E) be an undirected connected loop-free graph.Prove that…

Let G = (V,E) be an undirected connected loop-free graph. Suppose further that G is planar and determines 53 regions. If for some planar embedding of G, each regions has at least 5 edges in its ...
2
votes
3answers
546 views

Prove that Petersen's graph is non-planar using Euler's formula

Prove that Petersen's graph is non-planar using Euler's formula. I know that $n - m + f = 2$. But should I count $f$ and prove that the summation does not equal to two or solve to get $f =7$ and ...
0
votes
1answer
122 views

Planar and Euler's Formula Question

If a connected planar graph has four regions and six vertices, how many edges will the graph have? (I believe the answer is 8 but I'm not positive) 1) 9 2) 8 3) 6 4) 7 Graph A = ({a,b,c,d,e,f,g}, ...
11
votes
3answers
478 views

Can there exist an uncountable planar graph?

I'm currently revising a course on graph theory that I took earlier this year. While thinking about planar graphs, I noticed that a finite planar graph corresponds to a (finite) polygonisation of the ...
1
vote
1answer
44 views

Question on Planar Graph

Let $\delta$ denotes the minimum degree of vertex in a graph. For all planar graphs on $n$ vertices with $\delta\geq3$, which of the following is TRUE? $i)$ In any planar embedding, the number of ...
8
votes
2answers
118 views

Mathematicly Untangeling Untangle.

I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it. some free games: (but be warned highly addictive) Javascript: ...
0
votes
0answers
69 views

Question on Planar graphs

Consider a general planar graph, with no pair of vertexes being joined by more than one edge. Is there a upper limit of planer embeddings of such graph? That is, in how many ways maximum can such a ...
0
votes
1answer
100 views

can someone tell me if this graph contains subdivisions of both K5 and K3,3

Can someone tell me if this graph contains subdivisions of both $K_5$ and $K_{3,3}$ or not? The graph G1134 is non-planar My thought is that this graph subdivision of $K_{3,3}$ but not $K_5$. Is ...