On the realization of double occurrence words

DOI10.1016/J.DISC.2008.02.035zbMATH Open1205.05006arXiv0709.2933OpenAlexW1974972090MaRDI QIDQ1024503FDOQ1024503

Authors: L. Traldi, Blerta Shtylla, Louis Zulli 

Publication date: 17 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

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).

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

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

zbMATH Keywords

chord diagraminterlacement graphorthogonal projectioncircle graphGauss codedouble occurrence wordorthoprojection graph

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• Introduction to Vassiliev knot invariants
• On a characterization of Gauss codes
• Circle graph obstructions
• Virtual knot theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Gauss Realizability Problem
• On lacets and their manifolds
• A new proof of the Gauss interlace conjecture
• Title not available (Why is that?)
• AN EXTENSION OF THE JONES POLYNOMIAL OF CLASSICAL KNOTS
• A MATRIX INVARIANT OF CURVES IN S²

Cited In (14)

• Finite type invariants of nanowords and nanophrases
• Topological realizations of ortho-projection graphs
• Combinatorial methods for barcode analysis
• \texttt{Gauss-lintel}, an algorithm suite for exploring chord diagrams
• Orientation-preserving and orientation-reversing mappings: a new description
• Title not available (Why is that?)
• Comment on `Šilnikov-type orbits of Lorenz-family systems'
• Transformations of assembly number for 4-regular graphs
• Describing realizable Gauss diagrams using the concepts of parity or bipartite graphs
• Double occurrence words: their graphs and matrices
• Reductions on Double Occurrence Words
• A tight relation between series-parallel graphs and bipartite distance hereditary graphs
• 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)