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.

There's a well-established result which provides a lower bound for the crossing number of any simple undirected graph. However, is there any known result for an upper bound in this setting?

share|improve this question
    
If the graph has $m$ edges then $\binom{m}{2}$ is tight. You could object that you want to use straight lines, but that is not a requirement for the lower bound version of the problem. –  Chris Godsil Mar 14 '13 at 12:06

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.