On a Characterization of Gauss Codes

De Fraysseix, Hubert and Ossona de Mendez, Patrice (1999) On a Characterization of Gauss Codes. [Journal (Paginated)]

Full text not available from this repository.

Abstract

The traversal of a self crossing closed plane curve, with points of multiplicity at most two, defines a double occurrence sequence, the Gauss code of the curve. Using the D-switch operation, we give a new simple characterization of these sequences and deduce a simple self-contained proof of Rosenstiehl's characterization.

Item Type:Journal (Paginated)
Additional Information:10.1007/PL00009461
Classifications:G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.500 Representations
G Algorithms and Complexity > G.560 Geometry
ID Code:734

Repository Staff Only: item control page

References

A. Bouchet. Caractérisation des symboles croisés de genre nul. C.R. Acad. Sci., 274:724–727, 1972. (Paris).

H. de Fraysseix. Sur la représentation d’une suite à triples et à doubles occurrences par la suite des points d’intersection d’une courbe fermée du plan. In Problèmes combinatoires et théorie des graphes, volume 260 of Colloques internationaux C.N.R.S., pages 161–165. C.N.R.S., 1976.

H. de Fraysseix. Sur la représentation d’une suite à doubles et triples occurences par la suite de points d’intersection d’une courbe fermée du plan. In Problèmes combinatoire et théorie des graphes, volume 260, pages 161–165, 1978.

H. de Fraysseix. Local complementation and interlacement graphs. Discrete Mathematics, 33:29–35, 1981.

M. Dehn. über kombinatorische Topologie. Acta Math., 67:123–168, 1936. (Sweden).

H. Fleischner. Cycle decompositions, 2-coverings, removable cycles, and the fourcolor-disease. Progress in Graph Theory, pages 233–246, 1984.

G.K. Francis. Null genus realizability criterion for abstract intersection sequences. J. Combinatorial Theory, 7:331–341, 1969.

C.F. Gauss. Werke, pages 272 and 282–28. Teubner Leipzig, 1900.

A. Kotzig. Eulerian lines in finite 4-valent graphs and their transformations. In Proceedings of the Colloquium held at Tihany, Hungary, pages 219–230, 1969.

L. Lovasz and M.L. Marx. A forbidden subgraph characterization of gauss codes. Bull. Am. Math. Soc., 82:121–122, 1976.

M.L. Marx. The gauss realizability problem. Proc. Am. Math. Soc., 22:610–613, 1969.

J.V.Sz. Nagy. über ein topologisches Problem von Gauss. Math. Z., 26:579–592, 1927. (Paris).

R.C. Read and P. Rosenstiehl. On the Gauss crossing problem. In Colloquia Mathematica Societatis Janos Bolyai, pages 843–875, 1976. (Hungary).

R.C. Read and P. Rosenstiehl. On the principal edge tripartition of a graph. Annals of Discrete Maths, 3:195–226, 1978.

P. Rosenstiehl. A new proof of the Gauss interlace conjecture. Advances in Appl. Math., 23(1):3-13, 1999.

P. Rosenstiehl. Les graphes d’entrelacement d’un graphe. In Problèmes combinatoires et th´eorie des graphes, volume 260 of Colloques internationaux C.N.R.S., pages 359–362. C.N.R.S., 1976.

P. Rosenstiehl. Solution algebrique du problème de Gauss sur la permutation des points d’intersection d’une ou plusieurs courbes fermées du plan. C.R. Acad. Sci., 283 (A):551–553, 1976. (Paris).

P. Rosenstiehl and R.E. Tarjan. Gauss codes, planar hamiltonian graphs, and stack-sortable permutations. Jour. of Algorithms, 5:375–390, 1984.

H. Shank. The theory of left-right paths. In Combinatorial Math., volume III of Lecture Notes in Math., pages 42–54. Springer, 1975.

L.B. Treybig. A characterization of the double point structure of a projection of a polygonal knot in regular position. Trans. Am. Math Soc., 30:223–247, 1968.

W.T. Tutte. On unicursal paths in a network of degree 4. Amer. Math. Monthly, 4:233–237, 1941.