Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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 at 17:22
    
Ahh, I didn't see your comment. Thanks for answering though. –  user269037 Jan 20 at 18:11

2 Answers 2

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

Genus

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

share|improve this answer
    
Both computations are NP-hard, but (in your experience) is one measure easier in practice to obtain? –  hardmath Jan 21 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 at 19:50

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

share|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. –  Nicholas R. Peterson Jan 20 at 18:32

Your Answer

 
discard

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.