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

Author(s): Matheson; Tarjan

\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 ★★

Author(s): Oporowski; Zhao

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

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

\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 ★★


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

Author(s): Ghebleh; Zhu

\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

Syndicate content