𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Alternating diagrams of 4-regular graphs in 3-space

✍ Scribed by Jörg Sawollek

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
145 KB
Volume
93
Category
Article
ISSN
0166-8641

No coin nor oath required. For personal study only.

✦ Synopsis

Embeddings of 4-regular graphs into 3-space are examined by studying graph diagrams, i.e., projections of embedded graphs to an appropriate plane. An invariant of graph diagrams, first introduced by Yokota, is re-formulated and used to show that reduced alternating diagrams have minimal crossing number. The results presented here extend some of the so-called Tait Conjectures.

📜 SIMILAR VOLUMES

3-colorability of 4-regular hamiltonian
3-colorability of 4-regular hamiltonian graphs
✍ Herbert Fleischner; Gert Sabidussi 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 187 KB 👁 1 views

## Abstract On the model of the cycle‐plus‐triangles theorem, we consider the problem of 3‐colorability of those 4‐regular hamiltonian graphs for which the components of the edge‐complement of a given hamiltonian cycle are non‐selfcrossing cycles of constant length ≥ 4. We show that this problem is

Uniqueness of maximal dominating cycles
Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs
✍ Herbert Fleischner 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB 👁 2 views

## Abstract We construct 3‐regular (cubic) graphs __G__ that have a dominating cycle __C__ such that no other cycle __C__~1~ of __G__ satisfies __V(C)__ ⊆ __V__(__C__~1~). By a similar construction we obtain loopless 4‐regular graphs having precisely one hamiltonian cycle. The basis for these const

Triangulations of 3-way regular triparti
Triangulations of 3-way regular tripartite graphs of degree 4, with applications to orthogonal latin squares
✍ L.D. Andersen; A.J.W. Hilton 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 831 KB

If G is a regular tripartite graph of degree d(G) with tripartition (A,B,C) of V(G) such that the bipartite subgraphs induced by each ofA UB, BU C, CUA are all regular of degree ½d(G), then we call G 3-way regular. We give necessary and sufficient conditions for a 3-way regular tripartite graph of d

Orthogonal A-Trails of 4-Regular Graphs
Orthogonal A-Trails of 4-Regular Graphs Embedded in Surfaces of Low Genus
✍ Lars Døvling Andersen; André Bouchet; Bill Jackson 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 390 KB

Anton Kotzig has shown that every connected 4-regular plane graph has an A-trail, that is an Euler trail in which any two consecutive edges lie on a common face boundary. We shall characterise the 4-regular plane graphs which contain two orthogonal A-trails, that is to say two A-trails for which no

Voronoi Diagrams of Lines in 3-Space Und
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
✍ L.Paul Chew; Klara Kedem; Micha Sharir; Boaz Tagansky; Emo Welzl 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 261 KB

The combinatorial complexity of the Voronoi diagram of n lines in three dimensions under a convex distance function induced by a polytope with a constant Ž 2 Ž . . Ž . number of edges is shown to be O n ␣ n log n , where ␣ n is a slowly growing inverse of the Ackermann function. There are arrangemen