Stack Overflow
Stack Overflow

Questions tagged [planar-graph]

In graph theory, a planar graph is a graph that can be embedded in the plane without edge crossings.

In , a planar graph is a that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other.

Testing whether a graph is planar or not is called planarity testing. Kuratowski's theorem states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or K3,3 (the utility graph, a complete bipartite graph on six vertices, three of which connect to each of the other three). Such a subgraph is called a Kuratowski subgraph. There are many algorithms to determine whether a certain graph is planar, one of the best known of which is the Boyer-Myrvold algorithm in O(n) (where n is the number of vertices).

Use this tag if you have questions about planarity testing implementations, libraries, or planar graph issues more generally.

70 questions
22
votes
5 answers

Generate a large random planar graph

What is the most efficient way to generate a large (~ 300k vertices) random planar graph ("random" here means uniformly distributed)?
Marat Salikhov
  • 6,367
  • 4
  • 32
  • 35
15
votes
4 answers

How to check if a Graph is a Planar Graph or not?

I'm learning about the Planar Graph and coloring in c++. But i don't know install the algorithm to do this work. Someone please help me? Here i have some information for you! This is my code! And it still has a function does not finish. If someone…
Chelsea_cole
  • 1,055
  • 3
  • 15
  • 21
12
votes
2 answers

Minimizing number of crossings in a bipartite graph

The following algorithm problem occurred to me while drawing a graph for something unrelated: We have a plane drawing of a bipartite graph, with the disjoint sets arranged in columns as shown. How can we rearrange the nodes within each column so…
Imre Kerr
  • 2,388
  • 14
  • 34
11
votes
1 answer

Minimize Cross Edges in a Graph

I am using networkx (a python graph-drawing package) http://networkx.lanl.gov/index.html for one of my project. Though networkx is pretty cool, the display function kind of sucks due to number of cross edges. Is there a way to minimize cross edges…
Anil Katti
  • 1,313
  • 1
  • 14
  • 26
11
votes
2 answers

Planar Graph Layouts

What are some edge overlap minimization techniques when laying out a graph? (Preferably related to GraphViz) Also are there any existing software that can layout a graph in a planar fashion? Current Layout -…
jameszhao00
  • 7,213
  • 15
  • 62
  • 112
9
votes
3 answers

small cycle finding in a planar graph

I have a geometric undirected planar graph, that is a graph where each node has a location and no 2 edges cross, and I want to find all cycles that have no edges crossing them. Are there any good solutions known to this problem? What I'm planning…
BCS
  • 75,627
  • 68
  • 187
  • 294
9
votes
2 answers

Implementations of planar graphs/maps (with embeddings)

For the purpose of this post, by a plane graph, or a planar map, I will mean an abstract graph that can be drawn in the plane (or equivalently on the sphere), together with the circular order of the edges at every vertex according to a particular…
Lasse Rempe
  • 211
  • 3
  • 8
8
votes
1 answer

Connect an even number of nodes without intersection

I have two sets of n nodes. Now I want to connect each node from one set with another node from the other set. The resulting graph should have no intersections. I know of several sweep line algorithms (Bentley-Ottmann-Algorithm to check where…
Soift
  • 167
  • 7
7
votes
1 answer

List of problems that are in general NP-hard but have polynomial-time solution in planar graphs?

I encountered many problems that can be formulated as graph problem. It is in general NP-hard but sometimes the graph can be proved to be planar. Hence, I am interested in learning these problems and the algorithms. So far as I know: Max cut in…
Ivan Xiao
  • 1,919
  • 3
  • 19
  • 30
7
votes
1 answer

How to certify a planar embedding?

I am about to implement an algorithm for calculating a planar embedding. I have started to verify my results by running against a set of graphs (rome graphs) and comparing my results to the results of another implementation (yfiles). However, I can…
amoebe
  • 4,857
  • 5
  • 37
  • 42
6
votes
2 answers

Fastest Algorithm For Graph Planarization

I'm using Processing to develop a navigation system for complex data and processes. As part of that I have gotten into graph layout pretty deeply. It's all fun and my opinions on layout algorithms are : force-directed is for sissies (just look at it…
Cris Stringfellow
  • 3,714
  • 26
  • 48
6
votes
2 answers

Finding Hamiltonian cycles in cubic planar graphs

I have relatively small (40-80 nodes) cubic (3-regular) planar graphs, and I have to decide their Hamiltonicity. I am aware of the fact that this task is NP-complete, but I hope for asymptotically exponential time algorithms that are nevertheless…
Dániel Varga
  • 65
  • 1
  • 3
6
votes
4 answers

Open Source Graph Drawing program supporting Planar graph testing?

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. Their are many algorithms which exist for planar graph testing (i.e.…
brian
  • 173
  • 1
  • 3
  • 10
5
votes
2 answers

D3js Force-directed graph link intersections avoid

There is an example of force-directed graph i've tried to draw with the help of the d3.js. I have 3 big questions at all. And this is the code (you can run code snippet below, it might works): function getRandomInt(max, min = 0) { return…
Nick_Rimer
  • 191
  • 1
  • 9
5
votes
1 answer

Graph Planarity with Fixed Node Positions

I have an undirected graph with fixed node positions. The nodes cannot be moved, merged, removed or otherwise altered. The edges are fixed to their nodes, but do not have to be straight. I need to know if it possible to 'bend' or 'draw' the edges…
Henri
  • 205
  • 1
  • 9
1
2 3 4 5