Word-Representable Near-Triangulations

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 near-triangulation is a finite simple plane graph, with a specified crossing-free embedding, in which every bounded face has boundary a three-edge triangle; the unbounded face may have a longer boundary. Saying it contains $K_4$ means that four vertices are pairwise adjacent.

Statement recorded in the supplied source.

Give a complete necessary-and-sufficient structural characterization of those near-triangulations $G$ containing $K_4$ for which $\mathrm{WR}(G)$ holds. The $K_4$-containing class is part of the target; a characterization only of $K_4$-free near-triangulations does not answer it. [S2]

Short English statement

Determine exactly which plane graphs with triangular bounded faces and a four-vertex clique have a representing word.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1433 (GRAPH-046). 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.