{"id":"arxiv/2605.25733","url":"https://arxiv.org/abs/2605.25733","tags":["math.CO","cs.DM"],"score":0,"title":"Characterization of Word-Representable Near-Triangulations","domain":"math.CO","source":"arxiv","authors":["Suchanda Roy","Ramesh Hariharasubramanian"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-25","reactions":{}}