TOPICS
Search

Singlecross Graph


The term "singlecross graph" is used in this work to refer to a graph with graph crossing number 1. There appears to be no standard term for a graph with graph crossing number 1. In particular, the terms "almost planar graph" (e.g., Karpov 2014) and 1-planar graph (e.g., Fabrici and Madaras 2007, Brandenburg 2024) are used in the literature for different concepts.

A singlecross graph has graph genus 1 and is therefore a toroidal graph, since the single crossing can be removed by adding a handle. Not every toroidal graph is singlecross, however; for example, the complete graphs K_6 and K_7 have graph crossing numbers 3 and 9, respectively.

Möbius ladders on 2n vertices, with n>=3, are singlecross by construction.

Checking if a graph is singlecross is straightforward using the following algorithm (M. Haythorpe, pers. comm., Apr. 16, 2019). First, confirm that the graph is nonplanar. For each pair of edges (a,b) and (c,d) with four distinct endpoints, delete both edges and add a new vertex v joined to all four endpoints by the edges (a,v), (b,v), (c,v), and (d,v). The original graph is singlecross iff at least one of the resulting graphs is planar.

The numbers of singlecross simple graphs on n=1, 2, ... nodes are 0, 0, 0, 0, 1, 12, 162, 3183, 74696, 1892122, ... (OEIS A307071), and the numbers of connected graphs are 0, 0, 0, 0, 1, 11, 149, 3008, 71335, 1814021, ... (OEIS A307072).


See also

1-Planar Graph, Apex Graph, Critical Nonplanar Graph, Doublecross Graph, Graph Crossing Number, Planar Graph, Rectilinear Crossing Number, Toroidal Graph

Explore with Wolfram|Alpha

References

Brandenburg, F. J. "Straight-Line Drawings of 1-Planar Graphs." Comput. Geom. 116, 102036, 2024. https://doi.org/10.1016/j.comgeo.2023.102036.Fabrici, I. and Madaras, T. "The Structure of 1-Planar Graphs." Disc. Math. 307, 854-865, 2007. https://doi.org/10.1016/j.disc.2005.11.056.Karpov, D. V. "An Upper Bound on the Number of Edges in an Almost Planar Bipartite Graph." J. Math. Sci. 196, 737-746, 2014. https://doi.org/10.1007/s10958-014-1690-9.Sloane, N. J. A. Sequences A307071 and A307072 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Singlecross Graph

Cite this as:

Weisstein, Eric W. "Singlecross Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SinglecrossGraph.html

Subject classifications