A Short Proof of a Gauss Problem

De Fraysseix, Hubert and Ossona de Mendez, Patrice (1998) A Short Proof of a Gauss Problem. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 230-235 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_65).

Full text not available from this repository.

Abstract

A traversal of a self crossing closed plane curve, with points of multiplicity at most two, defines a double occurrence sequence. C.F. Gauss conjectured [2] that such sequences could be characterized by their interlacement properties. This conjecture was proved by P. Rosenstiehl in 1976 [15]. We shall give here a simple self-contained proof of his characterization. This new proof relies on the D-switch operation.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_65
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.560 Geometry
ID Code:82

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 fermeé 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. 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 four-color-disease. Progress in Graph Theory, pages 233-246, 1984.

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

C.F. Gauss. Werke, pages 272 and 282-286. 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. Trans Am. Math. Soc., 134:610-613, 1972.

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 János 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. Les graphes d'entrelacement d'un graphe. In Problèmes combinatoires et théorie des graphes, volume 260 of Colloques internationaux C.N.R.Ss., pages 359-362. C.N.R.S., 1976.

P. Rosenstiehl. Solution algébrique 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. A geometric proof of a Gauss crossing problem. (to appear).

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.

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