TOPICS
Search

Singlecross Graph


There appears to be no term in standard use for a graph with graph crossing number 1. Furthermore, the terms "almost planar" and "1-planar" are used in the literature for other concepts (e.g., Karpov 2013). Therefore, in this work, the term "singlecross graph" is used to mean a graph with graph crossing number 1.

Möbius ladders 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. Then, for all non-adjacent pairs of edges (a,b) and (c,d), delete the two edges and create a new vertex v. Finally, check if any one of the four new graphs obtained from adding any one of the edges (a,v), (b,v), (c,v), and (d,v) is planar. If so, then the original graph is singlecross.

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


See also

Apex Graph, Critical Nonplanar Graph, Doublecross Graph, Graph Crossing Number, Planar Graph, Rectilinear Crossing Number

Explore with Wolfram|Alpha

References

Karpov, D. V. "Upper Bound on the Number of Edges of an Almost Planar Bipartite Graph." 3 Jul 2013. https://arxiv.org/abs/1307.1013.Sloane, N. J. A. Sequences A307071 and A in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

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

Subject classifications