A bracket polynomial for graphs. II. Links, Euler circuits and marked graphs

Let $D$ be an oriented classical or virtual link diagram with directed universe $\vec{U}$. Let $C$ denote a set of directed Euler circuits, one in each connected component of $U$. There is then an associated looped interlacement graph $L(D,C)$ whose construction involves very little geometric information about the way $D$ is drawn in the plane; consequently $L(D,C)$ is different from other combinatorial structures associated with classical link diagrams, like the checkerboard graph, which can be difficult to extend to arbitrary virtual links. $L(D,C)$ is determined by three things: the structure of $\vec{U}$ as a 2-in, 2-out digraph, the distinction between crossings that make a positive contribution to the writhe and those that make a negative contribution, and the relationship between $C$ and the directed circuits in $\vec{U}$ arising from the link components; this relationship is indicated by marking the vertices where $C$ does not follow the incident link component(s). We introduce a bracket polynomial for arbitrary marked graphs, defined using either a formula involving matrix nullities or a recursion involving the local complement and pivot operations; the marked-graph bracket of $L(D,C)$ is the same as the Kauffman bracket of $D$. This provides a unified combinatorial description of the Jones polynomial that applies seamlessly to both classical and non-classical virtual links.