# zbMATH — the first resource for mathematics

Notes on the twisted graph. (English) Zbl 1374.05071
Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 119-125 (2012).
Summary: The twisted graph $$T _{n }$$ is a complete topological graph with $$n$$ vertices $$v _{1},v _{2},\dots ,v_{n}$$ in which two edges $$v_{i} v_{j}$$ ($$i<j$$) and $$v_{s } v_{t }$$ ($$s < t$$) cross each other if and only if $$i < s < t < j$$ or $$s < i < j < t$$. We study several properties concerning plane topological subgraphs of $$T _{n }$$.
For the entire collection see [Zbl 1253.68016].

##### MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory
##### Keywords:
alternating path; tree graph; max graph; matching graph
Full Text:
##### References:
 [1] Akiyama, J., Urrutia, J.: Simple alternating path problem. Discrete Math. 84(1), 101–103 (1990) · Zbl 0699.05032 · doi:10.1016/0012-365X(90)90276-N [2] Avis, D., Fukuda, K.: Reverse search enumeration. Discrete Applied Math. 6, 21–46 (1996) · Zbl 0854.68070 · doi:10.1016/0166-218X(95)00026-N [3] Hajnal, P., Mészáros, V.: Note on noncrossing alternating path in colored convex sets. Accepted in Discrete Mathematics and Theoretical Computer Science [4] Harborth, H., Mengersen, I.: Drawings of the complete graph with maximum number of crossings. In: Proceedings of the Graph Theory and Computing, Boca Raton, Fl. Congressus Numerantium, vol. 88, pp. 225–228. Utilitas Math., Winnipeg (1992) · Zbl 0792.05043 [5] Hernando, C., Hurtado, F., Noy, M.: Graphs of non-crossing perfect matchings. Graphs and Combin. 18, 517–532 (2002) · Zbl 1009.05110 · doi:10.1007/s003730200038 [6] Klazar, M.: Counting pattern-free set partitions II. Noncrossing and other hypergraphs. Electron. J. Combin. 7, Research Paper 34, 25 pages (2000) · Zbl 0944.05002 [7] Kynčl, J., Pach, J., Tóth, G.: Long alternating paths in bicolored point sets. Discrete Math. 308(19), 4315–4321 (2008) · Zbl 1168.05320 · doi:10.1016/j.disc.2007.08.013 [8] Lawson, C.L.: Software for C1-interpolation. In: Rice, J. (ed.) Mathematical Software III, pp. 161–194. Academic Press, New York (1977) · doi:10.1016/B978-0-12-587260-7.50011-X [9] Pach, J., Solymosi, J., Tóth, G.: Unavoidable configurations in complete topological graphs. Discrete Comput. Geom. 30, 311–320 (2003) · Zbl 1042.05030 · doi:10.1007/s00454-003-0012-9 [10] Rivera-Campo, E.: A Note on the Existente of Plane Spanning Trees of Geometrie Graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol. 1763, pp. 274–277. Springer, Heidelberg (2000) · Zbl 0956.05030 · doi:10.1007/978-3-540-46515-7_24
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.