Drawing Complete Multipartite Graphs on the Plane with Restrictions on Crossings

被引：23

作者：

Zhang, Xin ^{[1
]}

机构：

[1] Xidian Univ, Sch Math & Stat, Xian 710071, Peoples R China

来源：

ACTA MATHEMATICA SINICA-ENGLISH SERIES | 2014年 / 30卷 / 12期

基金：

中国国家自然科学基金;

关键词：

1-Planar graph; independent crossings; crossing number; NUMBER; 1-PLANARITY;

D O I：

10.1007/s10114-014-3763-6

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：2045 / 2053

页数：9

共 16 条

[1]

[Anonymous], 1971, RECENT TRENDS GRAPH, DOI DOI 10.1007/BFB0059432

[2] THE CROSSING NUMBER OF K1,3,N AND K2,3,N [J].

ASANO, K .

JOURNAL OF GRAPH THEORY, 1986, 10 (01) :1-8

[3]

Bondy JA, 2008, Grad. Texts Math, V244, DOI DOI 10.1007/978-1-84628-970-5

[4]

Borodin O. V., 1984, DISKRET ANAL, V41, P12

[5] A NEW PROOF OF THE 6 COLOR THEOREM [J].

BORODIN, OV .

JOURNAL OF GRAPH THEORY, 1995, 19 (04) :507-521

[6] 1-planarity of complete multipartite graphs [J].

Czap, Julius ;

Hudak, David .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (4-5) :505-512

[7]

de Klerk E, 2007, MATH PROGRAM, V109, P613, DOI 10.1007/s10107-006-0039-7

[8]

Ho PT, 2009, UTILITAS MATHEMATICA, V79, P125

[9] The crossing number of K1,4,n [J].

Huang, Yuanqiu ;

Zhao, Tinglei .

DISCRETE MATHEMATICS, 2008, 308 (09) :1634-1638

[10]

Kleitman D. J., 1970, Journal of Combinatorial Theory, Series A, V9, P315, DOI 10.1016/S0021-9800(70)80087-4

← 1 2 →