Triple Crossing Numbers of Graphs

We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero for planar graphs, and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings. In this paper, we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs.

The Crossing Number of Cartesian Products of Stars with 5-vertex Graphs II

The crossing number of cartesian products of paths and cycles with 5-vertex graphs mostly are known, but only few cartesian products of 5-vertex graphs with star K 1,n are known. In this paper, we will extent those results, and determine the crossing numbers of cartesian products of two 5-vertex graphs with star K 1,n .

THE PROJECTIVE PLANE CROSSING NUMBERS OF CIRCULAR GRAPHS

The authors give an upper bound for the projective plane crossing number of a circular graph. Also, the authors prove the projective plane crossing numbers of circular graph C （8, 3） and C （9, 3） are 2 and 1, respectively.

On the Crossing Numbers of K5 × Sn

By connecting the 5 vertices of K5 to other n vertices, we obtain a special family of graph denoted by Hn. This paper proves that the crossing number of Hn is Z（5, n） ＋2n＋ [n/2] ＋1, and the crossing number of Cartesian products of K5 with star Sn is Z（5, n） ＋ 5n ＋ [n/2] ＋ 1.

The Crossing Number of the Cartesian Products of Wm with Pn

Most results on crossing numbers of graphs focus on some special graphs, such as the Cartesian products of small graphs with path, star and cycle. In this paper, we obtain the crossing number formula of Cartesian products of wheel Wm with path Pn for arbitrary m ≥ 3 and n ≥ 1.

Two recursive inequalities for crossing numbers of graphs

In this paper, two recursive inequalities for crossing numbers of graphs are given by using basic counting method. As their applications, the crossing numbers of K1,3,n and K4,n ／ e are determined, respectively.

The Crossing Numbers of Cartesian-Products of Stars and 5-Vertex Graphs

In this paper, the crossing numbers of the Cartesian products of a specific 5-vertex graph with a star are given, and thus the result fills up the crossing number list of Cartesian products of all 5-vertex graphs with stars （presented by Marian Klesc）. In addition, we also give an up to date description of Cartesian products of 5-vertex graphs with stars, whose crossing numbers are known.

The Crossing Numbers of Cartesian Products of Stars with a 5-Vertex Graph

In this paper, we compute the crossing number of a specific graph Hn, and then by contraction, we obtain the conclusion that cr（G13 × Sn） = 4[n/2] [n-1/2]＋[n/2] . The result fills up the blank of the crossing numbers of Cartesian products of stars with all 5-vertex graphs presented by Marian Klesc.

The Crossing Number of Two-Maps on Orientable Surfaces

In this paper, we discuss the crossing numbers of two one-vertex maps on orientable surfaces. By using a reductive method, we give the crossing number of two one-vertex maps with one face on an orientable surface and the crossing number of a one-vertex map with one face and a one-vertex map with two faces on an orientable surface. This provides a lower bound for the crossing number of two general maps on an orientable surface.

A Nonconvex Nonorientable Crossing Number Sequence

It is well known that finding the crossing number of a graph on nonplanar surfaces is very difficult.In this paper we study the crossing number of the circular graph C（10,4） on the projective plane and determine the nonorientable crossing number sequence of C（10,4）.On the basis of the result,we show that the nonorientable crossing number sequence of C（10,4） is not convex.

Incompressible Pairwise Incompressible Surfaces in Knot Exteriors

We discuss the properties of incompressible pairwise incompressible surfaces in a knot complement by using twist crossing number. Let K be a pretzel knot or rational knot that its twistindex is less than 6, and let F be an incompressible pairwise incompressible surface in S 3-K. Then F is a punctured sphere.

Drawing Complete Multipartite Graphs on the Plane with Restrictions on Crossings

A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near independent crossings （say NIC-planar graph） is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex. The full characterization of NIC-planar complete and complete multipartite graphs is given in this paper.

Skewness of generalized Petersen graphs and related graphs

The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. In this paper, we determine the skewness of the generalized Petersen graph P（4k, k） and hence a lower bound for the crossing number of P（4k, k）. In addition, an upper bound for the crossing number of P（4k, k） is also given.

Properties ofπ-skew Graphs with Applications

The skewness of a graph G,denoted by sk(G),is the minimum number of edges in G whose removal results in a planar graph.It is an important parameter that measures how close a graph is to planarity,and it is complementary,and computationally equivalent,to the Maximum Planar Subgraph Problem.For any connected graph G on p vertices and q edges with girth g,one can easily verify that sk(G)≥π(G),whereπ(G)=[q−g/g−2(p−2)],and the graph G is said to beπ-skew if equality holds.The concept ofπ-skew was first proposed by G.L.Chia and C.L.Lee.Theπ-skew graphs with girth 3 are precisely the graphs that contain a triangulation as a spanning subgraph.The purpose of this paper is to explore the properties ofπ-skew graphs.Some families ofπ-skew graphs are obtained by applying these properties,including join of two graphs,complete multipartite graphs and Cartesian product of two graphs.We also discuss the threshold for the existence of a spanning triangulation.Among other results some sufficient conditions regarding the regularity and size of a graph,which ensure a spanning triangulation,are given.