On the Crossing Number of Circular Graphs
Tongyin Liu · Or Transactions · 1998
Let C(n, m) be a graph obtained from Cn by adding edges v1+v2+m(i = 1, 2, ... n. i +m (mod n)), where Cn is a circuit of order n and 2 ≤ m ≤. Then, C(n,m) is saidto be a circular graph. In this paper, we firstly evaluate the crossing number of C(n, m),if n = 2m (m ≥ 2). The crossing number of C(n, m) form = 2 and 3 are also observed. They are.andSecondlyl for general casel we provide an algorithm to evaluate the crossing numberof C(n,m) with the complexity O(n2). By the algorithm, we find an upper bound At last, based on these, we provide an algorithm to realize therectilinear immersion of C(n, m).