Tell me more ×
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.
up vote 2 down vote favorite

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
The tag graph is intended for questions about graphs of functions, see the tag-wiki and the tag-excerpt. (The tag-excerpt is also shown when you are adding a tag to a question.) There is a separate tag for graph-theory. – Martin Sleziak Mar 14 at 10:34
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 at 12:06

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.