Comparison of almost planar graphs

165 Views Asked by At

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.

2

There are 2 best solutions below

2
On BEST ANSWER

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

Genus

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

0
On

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