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. 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  and , delete the two edges and create a new vertex . Finally, check if any one of the four new graphs obtained from adding any one of the edges , , , and  is planar. If so, then the original graph is singlecross.

The numbers of singlecross simple graphs on  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).

---

REFERENCES

Sloane, N. J. A. Sequences A307071 and A in "The On-Line Encyclopedia of Integer Sequences."

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength