×

Outerplanar thrackles. (English) Zbl 1234.05168

Summary: We show that a graph drawing is an outerplanar thrackle if and only if, up to an inversion in the plane, it is Reidemeister equivalent to an odd musquash. This establishes Conway’s thrackle conjecture for outerplanar thrackles. We also extend this result in two directions. First, we show that no pair of vertices of an outerplanar thrackle can be joined by an edge in such a way that the resulting graph drawing is a thrackle. Secondly, we introduce the notion of crossing rank; drawings with crossing rank 0 are generalizations of outerplanar drawings. We show that all thrackles of crossing rank 0 are outerplanar. We also introduce the notion of an \(alternating\) cycle drawing, and we show that a thrackled cycle is alternating if and only if it is outerplanar.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Angenent S.: Parabolic equations for curves on surfaces. I. Curves with p-integrable curvature. Ann. Math. (2) 132(3), 451–483 (1990) · Zbl 0789.58070 · doi:10.2307/1971426
[2] Angenent S.: Parabolic equations for curves on surfaces. II. Intersections, blow-up and generalized solutions. Ann. Math. (2) 133(1), 171–215 (1991) · Zbl 0749.58054 · doi:10.2307/2944327
[3] Cairns G., Elton D.M.: The planarity problem for signed Gauss words. J. Knot Theory Ramif. 2(4), 359–367 (1993) · Zbl 0821.57010 · doi:10.1142/S0218216593000209
[4] Cairns G., Elton D.M.: The planarity problem. II. J. Knot Theory Ramif. 5(2), 137–144 (1996) · Zbl 0859.57013 · doi:10.1142/S0218216596000102
[5] Cairns G., King D.M.: The answer to Woodall’s musquash problem. Discret. Math. 207(1–3), 25–32 (1999) · Zbl 0934.05030 · doi:10.1016/S0012-365X(99)00130-2
[6] Cairns G., King D.M.: All odd musquashes are standard. Discret. Math. 226(1–3), 71–91 (2001) · Zbl 0968.05015 · doi:10.1016/S0012-365X(00)00126-6
[7] Cairns, G., McIntyre, M., Nikolayevsky, Y.: The thrackle conjecture for K 5 and K 3,3. In: Towards a Theory of Geometric Graphs. Contemp. Math. vol. 342, pp. 35–54. American Mathematical Society, Providence, RI (2004) · Zbl 1061.05026
[8] Cairns G., Nikolayevsky Y.: Bounds for generalized thrackles. Discret. Comput. Geom. 23(2), 191–206 (2000) · Zbl 0959.05030 · doi:10.1007/PL00009495
[9] Cairns G., Nikolayevsky Y.: Generalized thrackle drawings of non-bipartite graphs. Discret. Comput. Geom. 41(1), 119–134 (2009) · Zbl 1191.05032 · doi:10.1007/s00454-008-9095-5
[10] Chou K.-S., Zhu X.-P.: The Curve Shortening Problem. Chapman & Hall/CRC Press, Boca Raton (2001) · Zbl 1061.53045
[11] Grünbaum, B.: Arrangements and spreads. In: Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, vol. 10. American Mathematical Society, Providence, RI (1972) · Zbl 0249.50011
[12] Huisken G.: A distance comparison principle for evolving curves. Asian J. Math. 2(1), 127–133 (1998) · Zbl 0931.53032
[13] Lovász L., Pach J., Szegedy M.: On Conway’s thrackle conjecture. Discret. Comput. Geom. 18(4), 369–376 (1997) · Zbl 0892.05017 · doi:10.1007/PL00009322
[14] Pach, J.: Geometric graph theory. In: Surveys in combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser., vol. 267, pp. 167–200. Cambridge University Press Cambridge (1999) · Zbl 0931.05024
[15] Pach, J., Agarwal Pankaj, K.: Combinatorial geometry. In: Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1995) · Zbl 0881.52001
[16] Woodall, D.R.: Thrackles and deadlock. In: Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pp. 335–347. Academic Press, London (1971)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.