Hello, I've been struggling with a question about graph theory and I wanted a pointer as to what method to use to solve it, as the book I'm reading only describes a very unreliable method.

The question is simple. Prove that the following graph is or is not planar:

https://preview.redd.it/295hs2ouxjq61.png?width=170&format=png&auto=webp&s=ec4ce4d8b81132039650566027ac86a30066720e

Now, the book I'm following has a method for solving this kind of problem, but it's through trial and error. It first picks a node which has three connections and then a node connected to the first that has two other connections and tries to build a K3,3 homeomorph out of that. Here's an example:

https://preview.redd.it/qplx87pwyjq61.png?width=659&format=png&auto=webp&s=5582e0e32df79fb13651f1e574e651ff8d9465da

Problem is, if you can't do it with the nodes you chose, you have to choose a new set and try again, and do it over again until it works. And I'd be fine with that, but I'm studying for an admission test. I literally don't have the time to do this whole process until I guess it right.

Also, as a note, I already know that the answer to this problem is that the graph is not planar because it has a K3,3 homeomorph. So using a K5 homeomorph, for instance, wouldn't work. I need a different way to get to the K3,3.

So my question is: is there some other method of finding whether this graph is or is not planar? How would you do it?

And no, I'm not asking for you to do it for me, I just want to know the method so I can do it myself.

Thank you in advance!

I'm currently working on a problem involving planar graphs, while not absolutely necessary it would be nice if the graphical representation when calling g.show() would also show a planar graph. Is it possible to do this?

Edit: I think I've found a solution:

import networkx import mathplotlib.pyplot as plt networkx.draw_planar(G.networkx_graph())                                  
plt.show()

It has 8 vertices, 18 edges, but unknown faces. How can I move the vertices or edges to make the graph into 12-face graph according to Euler characteristic of planar graphs?

https://imgur.com/gallery/EXu0Bmb

I know in 3 dims an arbitrary graph can be presented with no edge intersections, but the analogy of planarity in 3D wouldn't be that it would be no intersections of 2D surfaces, I think. Does anyone know if there is a term for this, I swear I have read it before but cannot find it anywhere.

Hi,

I need to generate a random planar connected graph for a project, but I can't seem to find any algorithm to do that.

Could anyone point me to the right direction?

Thanks :)

Imagine a graph like a 2D crystal lattice, how would you calculate the total edges given number of nodes and the typical number edges?

Q.E.D.

I am working on a project where I need to generate simple planar graphs probably consisting of no more than 20-30 nodes/elements.

My first thought was to generate a grid, then randomly connect nodes to their nearest neighbor until all nodes have at least one connection.

This would work, but I wanted to see if there were any more elegant solutions that would be less computational and memory intensive.

Do you know of any approach or algorithm that minimizes edge lenght of a graph on a grid? I've been looking around, and every approach seems focused on minimizing the overall size, which leads to having some edges that are as long as the grid.

Is there any method that aims to have all edges as equally long as possible?

EDIT: after some tought (and help) I realized I'm trying to minimize weight, where weight repredents lenght difference relative to the longest edge. That means I can use arbitrarily big edges, as long as they're around the same weight, which means that vertices can have non iteger x,y coordinates.

As the question says.

I had this problem in my graph theory textbook, but I apparently keep doing something wrong. Pls help. So, the proof is apparent if a given graph has less than 6v. Then, I wanted to use the identity:

3v−6≥e

It should be true for every planar graph and I've seen it being succesfuly used with proving that every planar graph has at least one vertex of said degree. Now I decided to suppose a graph that has all of its vertices degree at least six, except for three such that I have:

e≥3(v-3)+2.5*3=3v-1.5

which is in contradiction with the previously mentioned identity. I've decided to make these three vertices degree 5, because I thought it to be the extreme case - if it works for this one, it should for all of them. The thing is... there must be 12 vertices of degree 5 to get rid of contradiction. And that is clearly absurd...

Hello!, with this problem I was thinking of using the 4 color theoren but I am not very sure if I can use it here, also, the fact that it's hamiltonian doesn't give me a clue of how to work with it, I would appretiate any kind of help :)

Hi!, i've seen the hints for this problem in MSE but I don't really know how to use/prove them so any help would be appretiated :)

To my understanding, all non-planar graphs are either K5 or K3,3 or have one of them as a subgraph. It is also my understanding that this is the only guaranteed criteria for distinguishing planar from non-planar, because Euler’s formula only pertains to planar graphs that are drawn as planar graphs and not their isomorphisms.

This means for a complicated graph, the only reliable way to see if it’s non-planar is to find K3,3 or K5 within it. Which seems like an incredibly tedious task which I hope never comes up on an exam.

Do planar graph questions really suck this much or do I have a misunderstanding?

https://preview.redd.it/m6qsawxn9vq41.png?width=480&format=png&auto=webp&s=5105a01e3010e1029bf6723ef18624b12ce98790

Hello!

I made a game based on the "Planar Graphs" video where you basically prove that various graphs are indeed planar, by "untying" them.

Thanks for checking this out!

https://scratch.mit.edu/projects/382594530/

One key property of a planar graph is that any two (distinct) paths with the same endpoints encloses some (perhaps disconnected) region in the plane. Or in simple terms a planar graph is one where 2 paths enclose a region in R^2 (and there is no way of entering the region without encountering one of the paths).

Ok, if you are browsing /r/math, you know where this is going: Is there any special meaning to a graph any three (distinct) paths with the same end points "enclose" a region in R^3? Of course, what "enclose" means is a bit nebulous above R^2, so that may be part of the issue. However, when viewed topologically it makes more sense: 2 paths in R^3 would create a the boundary of a 2-dimensional object, and 3 2-dimensional objects can be glued together like panels of an (American) football to "enclose" the whole region.

I for the n=3 case, I believe what I am looking for is called linklessly embeddable graphs, but I lack the topological background to make the concrete connection. But I feel as though this problem would have been studied more carefully elsewhere.

Any ideas?

Algorithms library for planar graphs (C++):

Graph represented as adjacency lists. Used STL containers and iterators. Implemented with OOP. This library for educational purposes and and very simple for understanding.

Github repository: https://github.com/AraKhachatryan/GraphAlgo

Printing graph as adjacency list:
 1  -->  2,  4
 2  -->  1,  4,  5
 3  -->  4,  6, 12, 13
 4  -->  1,  2,  3,  6,  7
 5  -->  2,  7
 6  -->  3,  4, 11, 12
 7  -->  4,  5, 10, 11
 8  --> 10, 16
 9  --> 10, 11, 15
10  -->  7,  8,  9, 16
11  -->  6,  7,  9, 14
12  -->  3,  6, 13
13  -->  3, 12
14  --> 11, 15
15  -->  9, 14, 16
16  -->  8, 10, 15

The graph class based on adjacency lists

typedef int vertex;
typedef std::pair<int, int> edge;
typedef std::vector<int> vertices;
typedef std::vector<edge> edges;
typedef std::map<vertex, vertices> neighborhood;

class graph 
{
private:
	edges m_edges;
	vertices m_vertices;
	neighborhood m_neighborhood;
        
public: //Helper
	void print_neighborhood() const; 

public:
	void remove_vertex(vertex);
	void remove_edge(vertex, vertex);
	
	bool is_vertex_in_graph(const vertex&) const;
	bool is_edge_in_graph(const edge&) const;
	bool is_edge_in_graph(const vertex&, const vertex&) const;
	
	neighborhood get_neighborhood() const;
	vertices get_neighbors(const vertex&);
	edges get_edges() const;
	vertices get_vertices() const;
	
	void add_neighborhood(const neighborhood&);
	void add_vertices(const vertices&);
	void add_vertex(const vertex&);
	void add_edges(const edges&);
	void add_edge(const vertex&, const vertex&);
	void add_edge(const edge&);
	
	graph(const neighborhood&);
	graph(const graph&);
	graph(); 
	~graph();
	graph& operator =(const graph&);
};

Implemented algorithms:

• Depth-first search algorithm (making spanning tree of input graph)
• Connectivity algorithm (determine whether a graph is connected and make graph's connected components vector)
• Biconnectivity algorithm (determine whether a graph is biconnected and and make graph's connected components vector)
• Dijkstra's shortest path algorithm of weighted

Hi, for my research work I need to test my algorithm on planar graphs. Networkx package has no random generator for planar graphs, and I didn't find any satisfying method yet on the web, so I'm wondering if you people know some specific generator or another way.

I would also be interested if some public libraries of planar graphs exist.

Hey everyone!

I'm in my second year of Computer Science and in one of my tests there was a question i couldn't answer. It went like this:

G is a planar connected graph where every vertix has a degree of 3, knowing the graph is composed, not exclusively, of pentagons, show that there are exactly 12 pentagons. How should i go about proving this? My thought process was :

1. Any vertix belonging to a pentagon needs atleast a degree of 2
2. If they all have a degree of 3 they can't belong to two pentagons unless they share an edge.
3. Where does this limitation of 12 come from?

And i couldn't proceed from there, any help?

Thanks!

There are some properties I've learned about a planar graph, such like Euler's formula and some corollary, but that's their property, if I want to determine a graph is planar or not, what can I do about it?

Here is the original problem that I stuck, G is a simple undirected planar graph with 9 vertices and they have the same degree. Prove or disprove that its complementary graph must have a Hamiltonian cycle.

By its property, I know the number of edge must be multiple of 9, then I try to illustrate by Dirac's theorem, but, before this, I have to claim "if G is a planar then its number of edge would be smaller than 27", what can I do for this? or something else can prove the question?

Give an example of a 2-connected nonhamiltonian planar graph with minimum vertex degree of 4.

Everyone likes making graphs, right? I'm pretty stuck after a few hours. I thought I'd solved it before my friend pointed out that my solution wasn't planar. My attempts are here: https://imgur.com/gallery/fA5NJKH

The first photo is my first solution with several vertices added at edge intersections to make it planar, but now it's hamiltonian. The second picture is a sketch of what I want in order to make it nonhamiltonian, but I'm not sure how to do that while keeping it planar and 2-connected.