Graph Theory » Topological G.T. » Crossing numbers

The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

Conjecture   $ \displaystyle cr(K_n) = \frac 14 \floor{\frac n2} \floor{\frac{n-1}2} \floor{\frac{n-2}2} \floor{\frac{n-3}2} $

Keywords: complete graph; crossing number

Posted by Robert Samal
updated July 28th, 2008
3 comments
Geometry » Polytopes

Hirsch Conjecture ★★★

Author(s): Hirsch

Conjecture   Let $ P $ be a convex $ d $-polytope with $ n $ facets. Then the diameter of the graph of the polytope $ P $ is at most $ n-d $.

Keywords: diameter; polytope

Posted by Robert Samal
updated July 9th, 2011
4 comments