Eulerian Graphs and Related Topics

I. Introduction. II. Three Pillars of Eulerian Graph Theory. Solution of a Problem Concerning the Geometry of Position. On the Possibility of Traversing a Line Complex Without Repetition or Interruption. From O. Veblen's ``Analysis situs''. III. Basic Concepts and Preliminary Results. Mixed Graphs and Their Basic Parts. Some Relations Between Graphs and (Mixed) (Di)graphs. Subgraphs. Graphs Derived from a Given Graph. Walks, Trails, Paths, Cycles, Trees; Connectivity. Compatibility, Cyclic Order of K * v and Corresponding Eulerian Trails. Matchings, 1-Factors, 2-Factors, 1-Factorizations, 2-Factorizations, Bipartite Graphs. Surface Embeddings of Graphs; Isomorphisms. Coloring Plane Graphs. Hamiltonian Cycles. Incidence and Adjacency Matrices, Flows and Tensions. Algorithms and Their Complexity. Final Remarks. IV. Characterization Theorems and Corollaries. Graphs. Digraphs. Mixed Graphs. Exercises. V. Euler Revisited and an Outlook on Some Generalizations. Trail Decomposition, Path/Cycle Decomposition. Parity Results. Double Tracings. Crossing the Border: Detachments of Graphs. Exercises. VI. Various Types of Eulerian Trails. Eulerian Trails Avoiding Certain Transitions. P(D)-Compatible Eulerian Trails in Digraphs. Aneulerian Trails in Bieulerian Digraphs and Bieulerian Orientations of Graphs. D 0 -Favoring Eulerian Trails in Digraphs. Pairwise Compatible Eulerian Trails. Pairwise Compatible Eulerian Trails in Digraphs. A-Trails in Plane Graphs. The Duality between A-Trails in Plane Eulerian Graphs and Hamiltonian Cycles in Plane Cubic Graphs. A-Trails and Hamiltonian Cycles in Eulerian Graphs. How to Find A-Trails: Some Complexity Considerations and Proposals for Some Algorithms. An A-Trail Algorithm for Arbitrary Plane Eulerian Graphs. Final Remarks on Non-Intersecting Eulerian Trails and A-Trails, and another Problem. Exercises. VII. Transformations of Eulerian Trails. Transforming Arbitrary Eulerian Trails in Graphs. Transforming Eulerian Trails of a Special Type. Applications to Special Types of Eulerian Trails and k 1 -Transformations. Transformation of Eulerian Trails in Digraphs. Final Remarks and Some Open Problems. Exercises. Bibliography. Index.