Characterization of Word-Representable Planar Graphs

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G=(V,E)$ be a finite simple undirected graph. A word over $V$ is a finite sequence of vertices in which every vertex occurs. For distinct $x,y\in V$, let $w|_{\{x,y\}}$ be the word obtained by deleting every letter other than $x,y$. They alternate when this restriction has no equal consecutive letters, that is, it has the form $xyxy\cdots$ or $yxyx\cdots$, of either even or odd length. The word $w$ represents $G$ when, for every distinct $x,y$, \[ xy\in E\quad\Longleftrightarrow\quad x,y\text{ alternate in }w. \] Write $\mathrm{WR}(G)$ when such a word exists.

A graph is planar if it can be drawn in $\mathbb R^2$ with different edges intersecting only at a shared endpoint.

Statement recorded in the supplied source.

Give a complete structural characterization, up to graph isomorphism, of \[ \{G:G\text{ is finite and planar},\ \mathrm{WR}(G)\}. \] The criterion must apply to arbitrary planar graphs, not only triangle-free graphs or near-triangulations. The general characterization by existence of a semi-transitive orientation is already known; the recorded request is for a structural description of the planar class. [S2]

Short English statement

Describe exactly which finite planar graphs can be encoded by a word whose alternating pairs are precisely their edges.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1431 (GRAPH-044). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Suchanda Roy and Ramesh Hariharasubramanian, Characterization of Word-Representable Near-Triangulations, arXiv:2605.25733v1 (2026), Sections 1--2, near-triangulation definition and word-representability. https://arxiv.org/pdf/2605.25733v1.
• S3 Magnus M. Halldórsson, Sergey Kitaev and Artem Pyatkin, Semi-Transitive Orientations and Word-Representable Graphs, arXiv:1501.07108v1 (2015), Section 1, definitions and general orientation characterization. https://arxiv.org/pdf/1501.07108v1.