Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have multiple graphs all of which are almost planar. Is there any existing terminology / method which compares them, such that one can say which one is more planar? This could simply be the required number of edge removal to make a graph planar.

All I want to know if there is a standard in the community.

share|cite|improve this question
It appears the term "crossing minimization" is used to measure how close a graph is to planar, but that long research has shown to be a difficult problem in practice. – hardmath Jan 20 '14 at 17:22
Ahh, I didn't see your comment. Thanks for answering though. – user269037 Jan 20 '14 at 18:11
up vote 1 down vote accepted

Crossing number.

For cubic graphs, the smallest graphs requiring 1, 2, 3, 4, 5, and 6 crossings are K33, Petersen, Heawood, Möbius-Kantor, Pappus, and Desargues (A fact I established with Geoff Exoo).


K7 can be embedded on a torus, so it's a genus 1 graph.

share|cite|improve this answer
Both computations are NP-hard, but (in your experience) is one measure easier in practice to obtain? – hardmath Jan 21 '14 at 17:00
Crossing number is currently easier to calculate, because the program is written. I don't know of an existing "is this graph toroidal?" checker, but I'd love to run it on a bunch of graphs if someone has it. – Ed Pegg Jan 21 '14 at 19:50

Okay I found it. On the Crossing Number of Almost Planar Graphs.

share|cite|improve this answer
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. – Nick Peterson Jan 20 '14 at 18:32

Graph skewness is another measure of how planar graph a graph is. It follows the definition that you suggested: the minimal number of edges that have to be removed to make the graph planar.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.