# planar graph

## 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

## Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

\begin{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? \end{conjecture}

Keywords: planar graph; polynomial algorithm

## Approximation ratio for k-outerplanar graphs ★★

Author(s): Bentz

\begin{conjecture} Is the approximation ratio for the \emph{Maximum Edge Disjoint Paths} (MaxEDP) or the \emph{Maximum Integer Multiflow} problem (MaxIMF) bounded by a constant in $k$-outerplanar graphs or tree-width graphs? \end{conjecture}

Keywords: approximation algorithms; planar graph; polynomial algorithm

## Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

\begin{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? \end{conjecture}

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

## Domination in plane triangulations ★★

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

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

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

For a graph $G$, we let $cr(G)$ denote the \Def[crossing number]{Crossing number (graph theory)} of $G$, and we let $\omega(G)$ denote the size of the largest complete subgraph of $G$.

\begin{question} Does every graph $G$ with $cr(G) \le 5$ and $\omega(G) \le 5$ have a 5-coloring? \end{question}

Keywords: coloring; crossing number; planar graph

## Jones' conjecture ★★

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

\begin{conjecture} For every planar graph $G$, $cc(G)\leq 2cp(G)$. \end{conjecture}

Keywords: cycle packing; feedback vertex set; planar graph

## 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$.

\begin{problem} What is the maximal possible \Def[oriented chromatic number]{Oriented_coloring} of an oriented planar graph? \end{problem}

Keywords: oriented coloring; oriented graph; planar graph

## Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

\begin{conjecture} Every planar graph of girth $\ge 4k$ has a homomorphism to $C_{2k+1}$. \end{conjecture}

Keywords: girth; homomorphism; planar graph

## Circular coloring triangle-free subcubic planar graphs ★★

\begin{problem} Does every triangle-free planar graph of maximum degree three have circular chromatic number at most $\frac{20}{7}$? \end{problem}

Keywords: circular coloring; planar graph; triangle free