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

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