Graph Theory

Obstacle number of planar graphs ★

Author(s): Alpert; Koch; Laison

Does there exist a planar graph with obstacle number greater than 1? Is there some $ k $ such that every planar graph has obstacle number at most $ k $?

Keywords: graph drawing; obstacle number; planar graph; visibility graph

Posted by Andrew King
updated November 23rd, 2011
add new comment
Topology

Upgrading a multifuncoid ★★

Author(s): Porton

Let $ \mho $ be a set, $ \mathfrak{F} $ be the set of filters on $ \mho $ ordered reverse to set-theoretic inclusion, $ \mathfrak{P} $ be the set of principal filters on $ \mho $, let $ n $ be an index set. Consider the filtrator $ \left( \mathfrak{F}^n ; \mathfrak{P}^n \right) $.

Conjecture   If $ f $ is a multifuncoid of the form $ \mathfrak{P}^n $, then $ E^{\ast} f $ is a multifuncoid of the form $ \mathfrak{F}^n $.

See below for definition of all concepts and symbols used to in this conjecture.

Refer to this Web site for the theory which I now attempt to generalize.

Keywords:

Posted by porton
updated October 9th, 2011
add new comment
Graph Theory » Coloring » Labeling

Good edge labeling and girth ★★

Author(s): Bode-Farzad-Theis

Conjecture   Every graph with large girth has a good edge labeling.

More specifically: there exists a constant $ g $ such that every graph with girth at least $ g $ has a good edge labeling.

Keywords: good edge labeling, edge labeling

Posted by DOT
updated September 15th, 2012
2 comments
Geometry » Polytopes

Extension complexity of (convex) polygons ★★

Author(s):

The extension complexity of a polytope $ P $ is the minimum number $ q $ for which there exists a polytope $ Q $ with $ q $ facets and an affine mapping $ \pi $ with $ \pi(Q) = P $.

Question   Does there exists, for infinitely many integers $ n $, a convex polygon on $ n $ vertices whose extension complexity is $ \Omega(n) $?

Keywords: polytope, projection, extension complexity, convex polygon

Posted by DOT
updated August 13th, 2011
add new comment