Topological realizations of ortho-projection graphs (Q842981)

The present paper takes into account ortho-projection graphs, i.e. undirected, looped graphs \(G\) (without multiple loops and without multiple edges) satisfying the following adjacency condition: arbitrary (not necessarily distinct) vertices are neighbors in \(G\) if and only if they have an odd number of common neighbors. These graphs, which arise arise naturally in knot theory and in low-dimensional topology, are closely related to circle graphs (see for example [\textit{A. Bouchet}, J. Comb. Theory, Ser. B 60, No.~1, 107--144 (1994; Zbl 0793.05116) and \textit{H. de Fraysseix}, Eur. J. Comb. 5, 223--238 (1984; Zbl 0551.05056)]); in particular, in [\textit{B. Shtylla, L. Traldi} and \textit{L. Zulli}, Discrete Math. 309, No. 6, 1769--1773 (2009; Zbl 1205.05006)], interesting relations are proved to exist between ortho-projection graphs and the problem of realizing circle graphs by generic closed curves. Here, the authors discuss the production of ortho-projection graphs from alternating knot diagrams, and introduce a more general construction of such graphs from splittings of closed, non-orientable surfaces. As their main result, they prove that this new topological construction generates all ortho-projection graphs. Moreover (despite the computer assisted analysis proving that each ortho-projection graph with eight or fewer vertices is the looped interlacement graph of an alternating classical knot diagram [see \textit{B. Shtylla, L. Traldi} and \textit{L. Zulli}, J. Knot Theory Ramifications 15, No. 1, 81--100 (2006; Zbl 1093.57008)]), they present a minimal example of an ortho-projection graph that does not arise from a knot diagram, and provide a surface-splitting that realizes this graph.