On the realization of double occurrence words

DOI10.1016/J.DISC.2008.02.035MaRDI QIDQ1024503zbMATH OpenOpenAlexFDO

Authors L. Traldi, Blerta Shtylla, Louis Zulli

Publication date 17 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0709.2933

zbMATH Keywords

chord diagraminterlacement graphorthogonal projectioncircle graphGauss codedouble occurrence wordorthoprojection graph

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: Let S be a double occurrence word, and let M_S be the word's interlacement matrix, regarded as a matrix over GF(2). Gauss addressed the question of which double occurrence words are realizable by generic closed curves in the plane. We reformulate answers given by Rosenstiehl and by de Fraysseix and Ossona de Mendez to give new graph-theoretic and algebraic characterizations of realizable words. Our algebraic characterization is especially pleasing: S is realizable if and only if there exists a diagonal matrix D_S such that M_S+D_S is idempotent over GF(2).

Recommendations

• A new proof of the Gauss interlace conjecture
• The common structure of the curves having a same Gauss word
• scientific article; zbMATH DE number 7274002
• On a characterization of Gauss codes
• A characterization of plane Gauss paragraphs

Cites work

• scientific article; zbMATH DE number 3536116 (Why is no real title available?)
• scientific article; zbMATH DE number 3537726 (Why is no real title available?)
• scientific article; zbMATH DE number 2107523 (Why is no real title available?)
• A MATRIX INVARIANT OF CURVES IN S²
• A new proof of the Gauss interlace conjecture
• AN EXTENSION OF THE JONES POLYNOMIAL OF CLASSICAL KNOTS
• Circle graph obstructions
• Introduction to Vassiliev knot invariants
• On a characterization of Gauss codes
• On lacets and their manifolds
• The Gauss Realizability Problem
• Virtual knot theory

Cited in

(15)

• Finite type invariants of nanowords and nanophrases
• Topological realizations of ortho-projection graphs
• \texttt{Gauss-lintel}, an algorithm suite for exploring chord diagrams
• Combinatorial methods for barcode analysis
• Orientation-preserving and orientation-reversing mappings: a new description
• scientific article; zbMATH DE number 554160 (Why is no real title available?)
• Comment on `Šilnikov-type orbits of Lorenz-family systems'
• Transformations of assembly number for 4-regular graphs
• Double occurrence words: their graphs and matrices
• Describing realizable Gauss diagrams using the concepts of parity or bipartite graphs
• Reductions on Double Occurrence Words
• A tight relation between series-parallel graphs and bipartite distance hereditary graphs
• Parity conditions for realizability of Gauss diagrams
• Ordered unavoidable sub-structures in matchings and random matchings
• Symbol Separation in Double Occurrence Words

This page was built for publication: On the realization of double occurrence words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024503)