# Comparison of almost planar graphs

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.

-
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

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).

Genus

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

-
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.

-
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.

-