Tessellation and Visibility Representations of Maps on the Torus

The model of the torus as a parallelogram in the plane with opposite sides identified enables us to define two families of parallel lines and to tessellate the torus, then to associate to each tessellation a toroidal map with an upward drawing. It is proved that a toroidal map has a tessellation representation if and only if its universal cover is 2-connected. Those graphs that admit such an embedding in the torus are characterized. Received November 22, 1995, and in revised form May 1, 1997.     

Ueber die Farbenreactionen des Anilins, des Pseudotoluidins und des Toluidins

Ohne Zusammenfassung     

Quantitative Bestimmung von Paratoluidin neben Orthotoluidin

Ohne Zusammenfassung     

Ueber die Erkennung von Anilin neben Toluidin

Ohne Zusammenfassung     

Rectilinear planar layouts and bipolar orientations of planar graphs

We propose a linear-time algorithm for generating a planar layout of a planar graph. Each vertex is represented by a horizontal line segment and each edge by a vertical line segment. All endpoints of the segments have integer coordinates. The total space occupied by the layout is at mostn by at most 2n–4. Our algorithm, a variant of one by Otten and van Wijk, generally produces a more compact layout than theirs and allows the dual of the graph to be laid out in an interlocking way. The algorithm is based on the concept of abipolar orientation. We discuss relationships among the bipolar orientations of a planar graph.Research partly supported by the Agence de L'Informatique du Ministere de L'Industrie, France, under contract No. 83-285.     

A characterization of planar graphs by trémaux orders

A new characterization of planar graphs is stated in terms of an order relation on the vertices, called the Trémaux order, associated with any Trémaux spanning tree or Depth-First-Search Tree. The proof relies on the work of W. T. Tutte on the theory of crossings and the Trémaux algebraic theory of planarity developed by P. Rosenstiehl.     

Gauss codes,planar hamiltonian graphs,and stack-sortable permutations

In this paper the following three recognition problems are considered: (1) Test whether a given sequence is the Gauss code of a planar self-intersecting curve; (2) test whether a given graph with a known Hamiltonian cycle is planar; and (3) test whether a given permutation can be sorted using two stacks in parallel. These three problems are closely related: A simple linear-time algorithm that solves all three is described. The heart of the algorithm is a data structure, previously used in general planarity testing, called a pile of twin stacks.     

Ueber die Trennung von Alizarin und Purpurin

Ohne Zusammenfassung     

Transitivity And Connectivity Of Permutations

It was observed for years, in particular in quantum physics, that the number of connected permutations of [0; n] (also called indecomposable permutations), i. e. those such that for any i < n there exists j > i with (j) < i, equals the number of pointed hypermaps of size n, i. e. the number of transitive pairs (, ) of permutations of a set of cardinality n with a distinguished element.The paper establishes a natural bijection between the two families. An encoding of maps follows. To Chantal, that we may stay connected beyond the simple line of time.