Characterization of Word-Representable Near-Triangulations
2026-05-25 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a special kind of graph called word-representable graphs, where connections between points can be described by patterns in a word. They focus on near-triangulations, which are graphs drawn so that all inner areas look like triangles. The authors provide a full list of small patterns that cannot appear inside these graphs if they are to be word-representable. Their findings bring together and improve past results on different types of near-triangulations and fix some earlier mistakes.
word-representable graphsnear-triangulationplanar graphinduced subgraphgraph orientationcombinatorics on wordsgraph coloringpolyomino triangulationforbidden subgraph characterization
Authors
Suchanda Roy, Ramesh Hariharasubramanian
Abstract
A graph $G=(V,E)$ is said to be word-representable if there exists a word $w$ over the alphabet $V$ such that two distinct letters $x,y\in V$ alternate in $w$ if and only if $xy \in E$. Word-representable graphs form a well-studied graph class with connections to graph orientations, combinatorics on words, and graph coloring. A near-triangulation is a planar graph in which every face except the outer face is a triangle. Several subclasses of near-triangulations have previously been investigated in the context of word-representability, including polyomino triangulations, triangulations of rectangular polyominoes with a single domino tile, $K_4$-free near-triangulations, face subdivisions of triangular grid graphs, triangulations of grid-covered cylinder graphs, and chordal near-triangulations. In this paper, we obtain a complete characterization of word-representable near-triangulations in terms of forbidden induced subgraphs. Our result unifies and extends the previously known characterizations for the above subclasses, while also correcting inaccuracies appearing in earlier works.