planar graph

Obstacle number of planar graphs ★

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

Graph Theory

Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

Conjecture It has been shown that a $k$ -outerplanar embedding for which $k$ is minimal can be found in polynomial time. Does a similar result hold for $k$ -edge-outerplanar graphs?

Keywords: planar graph; polynomial algorithm

Posted by jcmeyer
updated April 18th, 2010

add new comment

Graph Theory

Approximation ratio for k-outerplanar graphs ★★

Author(s): Bentz

Conjecture Is the approximation ratio for the Maximum Edge Disjoint Paths (MaxEDP) or the Maximum Integer Multiflow problem (MaxIMF) bounded by a constant in $k$ -outerplanar graphs or tree-width graphs?

Keywords: approximation algorithms; planar graph; polynomial algorithm

Posted by jcmeyer
updated April 18th, 2010

add new comment

Graph Theory

Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

Conjecture Can the approximation ratio $O(\sqrt{n})$ be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than $\mathcal{APX}$ -hardness?

Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm

Posted by jcmeyer
updated April 18th, 2010

add new comment

Graph Theory » Topological G.T.

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture Every sufficiently large plane triangulation $G$ has a dominating set of size $\le \frac{1}{4} |V(G)|$ .

Keywords: coloring; domination; multigrid; planar graph; triangulation

Posted by mdevos
updated May 4th, 2009

add new comment

Graph Theory » Topological G.T. » Coloring

5-coloring graphs with small crossing & clique numbers ★★

Author(s): Oporowski; Zhao

For a graph $G$ , we let $cr(G)$ denote the crossing number of $G$ , and we let $\omega(G)$ denote the size of the largest complete subgraph of $G$ .

Question Does every graph $G$ with $cr(G) \le 5$ and $\omega(G) \le 5$ have a 5-coloring?

Keywords: coloring; crossing number; planar graph

Posted by mdevos
updated October 9th, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

Jones' conjecture ★★

Author(s): Kloks; Lee; Liu

For a graph $G$ , let $cp(G)$ denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let $cc(G)$ denote the cardinality of a minimum feedback vertex set (set of vertices $X$ so that $G-X$ is acyclic).

Conjecture For every planar graph $G$ , $cc(G)\leq 2cp(G)$ .

Keywords: cycle packing; feedback vertex set; planar graph

Posted by cmlee
updated December 5th, 2019

3 comments

Graph Theory » Coloring » Vertex coloring

Oriented chromatic number of planar graphs ★★

Author(s):

An oriented colouring of an oriented graph is assignment $c$ of colours to the vertices such that no two arcs receive ordered pairs of colours $(c_1,c_2)$ and $(c_2,c_1)$ . It is equivalent to a homomorphism of the digraph onto some tournament of order $k$ .