zbMATH — the first resource for mathematics

Generalized thrackle drawings of non-bipartite graphs. (English) Zbl 1191.05032
Summary: A graph drawing is called a generalized thrackle if every pair of edges meets an odd number of times. In a previous paper, we showed that a bipartite graph \(G\) can be drawn as a generalized thrackle on an oriented closed surface \(M\) if and only if \(G\) can be embedded in \(M\). In this paper, we use Lins’ notion of a parity embedding and show that a non-bipartite graph can be drawn as a generalized thrackle on an oriented closed surface \(M\) if and only if there is a parity embedding of \(G\) in a closed non-orientable surface of Euler characteristic \(\chi (M) - 1\). As a corollary, we prove a sharp upper bound for the number of edges of a simple generalized thrackle.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C62 Graph representations (geometric and intersection representations, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX Cite
Full Text: DOI
[1] Archdeacon, D., A Kuratowski theorem for the projective plane, J. Graph Theory, 5, 243-246, (1981) · Zbl 0464.05028
[2] Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1974) · Zbl 0284.05101
[3] Berger, M., Gostiaux, B.: Differential Geometry: Manifolds, Curves, and Surfaces. Graduate Texts in Mathematics, vol. 115. Springer, New York (1988) · Zbl 0629.53001
[4] Bredon, G.E.: Topology and Geometry. Graduate Texts in Mathematics, vol. 139. Springer, New York (1997) · Zbl 0934.55001
[5] Cairns, G.; Nikolayevsky, Y., Bounds for generalized thrackles, Discrete Comput. Geom., 23, 191-206, (2000) · Zbl 0959.05030
[6] Cairns, G.; McIntyre, M.; Nikolayevsky, Y.; Pach, J. (ed.), The thrackle conjecture for \(K\_{}\{5\}\) and \(K\_{}\{3,3\}, (2004),\) Providence · Zbl 1061.05026
[7] Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2005) · Zbl 1074.05001
[8] Dieudonné, J.: A History of Algebraic and Differential Topology. 1900-1960. Birkhäuser, Boston (1989) · Zbl 0673.55002
[9] Dubrovin, B.A., Fomenko, A.T., Novikov, S.P.: Modern Geometry, Part III. Springer, Berlin (1990) · Zbl 0703.55001
[10] Edelen, D.G.B.: Applied Exterior Calculus. Dover, New York (2005) · Zbl 1099.58001
[11] Giblin, P.J.: Graphs, Surfaces and Homology. Chapman & Hall, Boca Raton (1981) · Zbl 0477.57001
[12] Gross, J.L., Tucker, T.W.: Topological Graph Theory. Dover, New York (2001) · Zbl 0991.05001
[13] Grove, L.C.: Classical Groups and Geometric Algebra. Graduate Studies in Mathematics, vol. 39. Am. Math. Soc., Providence (2002)
[14] Lins, S., Combinatorics of orientation reversing polygons, Aequ. Math., 29, 123-131, (1985) · Zbl 0592.05019
[15] Lovász, L.; Pach, J.; Szegedy, M., On Conway’s thrackle conjecture, Discrete Comput. Geom., 18, 368-376, (1997) · Zbl 0892.05017
[16] Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Press, Baltimore (2001) · Zbl 0979.05002
[17] Perlstein, A., Pinchasi, R.: Generalized thrackles and geometric graphs in ℝ3 with no pair of strongly avoiding edges. Preprint · Zbl 1188.05055
[18] Prasolov, V.V.: Elements of Combinatorial and Differential Topology. Graduate Studies in Mathematics, vol. 74. Am. Math. Soc., Providence (2006) · Zbl 1098.57001
[19] Woodall, D. R., Thrackles and deadlock, 335-347, (1971), San Diego · Zbl 0213.50603
[20] Woodall, D. R., Unsolved problems, 359-363, (1972), Oxford
[21] Zaslavsky, T., The projective-planar signed graphs, Discrete Math., 113, 223-247, (1993) · Zbl 0779.05018
[22] Zaslavsky, T., The order upper bound on parity embedding of a graph, J. Comb. Theory Ser. B, 68, 149-160, (1996) · Zbl 0856.05030
[23] Zieschang, H., Vogt, E., Coldewey, H.-D.: Surfaces and Planar Discontinuous Groups. Lecture Notes in Mathematics, vol. 835. Springer, Berlin (1980) · Zbl 0438.57001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.