Let D be an oriented classical or virtual link diagram with directed universe (U) over right arrow. 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 di. cult to extend to arbitrary virtual links. L(D, C) is determined by three things: the structure of (U) over right arrow 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 (U) over right arrow 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.
A bracket polynomial for graphs, II. Links, Euler circuits and marked graphs