TOPICS
Search

Singlecross Graph


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 2013) and 1-planar graph (e.g., Fabrici and Madaras 2007, Brandenburg 2021) are used in the literature for a different concepts. In this work, the term "singlecross graph" is therefore used to refer to 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

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

Explore with Wolfram|Alpha

References

Brandenburg, F. J. "Straight-Line Drawings of 1-Planar Graphs." 3 Sep 2021. https://arxiv.org/abs/2109.01692.Fabrici, I. and Madaras, T. "the Structure of 1-Planar Graphs." Disc. Math. 307, 854-865, 2007.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