Sequentially embeddable graphs
| Autor: | Autry, Jackson, O'Neill, Christopher |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We call a (not necessarily planar) embedding of a graph $G$ in the plane \emph{sequential} if its vertices lie in $\mathbb Z^2$ and the line segments between adjacent vertices contain no interior integer points. In this note, we prove (i) a graph $G$ has a sequential embedding if and only if $G$ is 4-colorable, and (ii) if $G$ is planar, then $G$ has a sequential planar embedding. |
| Databáze: | arXiv |
| Externí odkaz: |
|