Graphs that admit right angle crossing drawings

被引：17

作者：

Arikushi, Karin ^{[2
]}

Fulek, Radoslav ^{[1
]}

Keszegh, Balazs ^{[1
,3
]}

Moric, Filip ^{[1
]}

Toth, Csaba D. ^{[2
]}

机构：

[1] Ecole Polytech Fed Lausanne, CH-1015 Lausanne, Switzerland

[2] Univ Calgary, Calgary, AB T2N 1N4, Canada

[3] Alfred Renyi Inst Math, Budapest, Hungary

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2012年 / 45卷 / 04期

基金：

加拿大自然科学与工程研究理事会; 瑞士国家科学基金会;

关键词：

Discharging; Crossing lemma; Polyline drawing; Right angle crossing drawing; Archimedean tiling;

D O I：

10.1016/j.comgeo.2011.11.008

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends per edge, then the number of edges is at most 6.5n and 74.2n, respectively. This is a strengthening of a recent result of Didimo et al. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：169 / 177

页数：9

共 14 条

[1] On the maximum number of edges in quasi-planar graphs [J].

Ackerman, Eyal ;

Tardos, Gabor .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 2007, 114 (03) :563-571

[2]

Ajtai M., 1982, THEORY PRACTICE COMB, P9, DOI [10.1016/S0304-0208(08), DOI 10.1016/S0304-0208(08), DOI 10.1016/S0304-0208(08)73484-4]

[3]

Angelini P, 2010, LECT NOTES COMPUT SC, V5849, P21, DOI 10.1007/978-3-642-11805-0_5

[4]

[Anonymous], LNCS

[5] SOLUTION OF 4-COLOR-MAP PROBLEM [J].

APPEL, K ;

HAKEN, W .

SCIENTIFIC AMERICAN, 1977, 237 (04) :108-&

[6]

Di Giacomo E, 2010, LECT NOTES COMPUT SC, V5849, P15, DOI 10.1007/978-3-642-11805-0_4

[7]

Didimo W, 2009, LECT NOTES COMPUT SC, V5664, P206, DOI 10.1007/978-3-642-03367-4_19

[8]

DUJMOVIC V, 2010, P 16 S COMP AUSTR TH, V109, P19

[9]

Hlineny P., 2000, LECT TEXT SPRING SCH

[10]

Huang WD, 2008, IEEE PACIFIC VISUALISATION SYMPOSIUM 2008, PROCEEDINGS, P41

← 1 2 →