zbMATH — the first resource for mathematics

Enumeration of simple complete topological graphs. (English) Zbl 1341.05126
Márquez, Alberto (ed.) et al., Proceedings of the 4th European conference on combinatorics, graph theory and applications, EuroComb’07, Seville, Spain, September 11–15, 2007. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 29, 295-299 (2007).
Summary: A simple topological graph \(T=(V(T),E(T))\) is a drawing of a graph in the plane, where every two edges have at most one common point (an end-point or a crossing) and no three edges pass through a single crossing. Topological graphs \(G\) and \(H\) are isomorphic if \(H\) can be obtained from \(G\) by a homeomorphism of the sphere, and weakly isomorphic if \(G\) and \(H\) have the same set of pairs of crossing edges. We prove that the number of isomorphism classes of simple complete topological graphs on \(n\) vertices is \(2^{\Theta (n^{4})}\). We also show that the number weak isomorphism classes of simple complete topological graphs with \(n\) vertices and \(\binom {n}{4}\) crossings is at least \(2^{n(\log n - O(1))}\), which improves the estimate of H. Harborth and I. Mengersen [in: Proceedings of the twenty-third Southeastern international conference on combinatorics, graph theory, and computing, held at Florida Atlantic University, Boca Raton, FL, USA, February 3–7, 1992. Winnipeg: Utilitas Mathematica Publishing Inc.. 225–228 (1992; Zbl 0792.05043)].
For the entire collection see [Zbl 1137.05002].

05C30 Enumeration in graph theory
Full Text: DOI
[1] Felsner, S., On the number of arrangements of pseudolines, (), 257-267 · Zbl 0891.05005
[2] Goodman, J.E., Proof of a conjecture of burr, grünbaum, and sloane, Discrete mathematics, 32, 27-35, (1980) · Zbl 0444.05029
[3] Harborth, H.; Mengersen, I., Drawings of the complete graph with maximum number of crossings, (), 225-228 · Zbl 0792.05043
[4] Kynčl, J., “Crossings in topological graphs”, master thesis, Charles University, Prague (2006)
[5] Pach, J.; Tóth, G., How many ways can one draw a graph?, (), 47-58 · Zbl 1215.05091
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.