首页    期刊浏览 2024年07月19日 星期五
登录注册

文章基本信息

  • 标题:Notes on Large Angle Crossing Graphs
  • 本地全文:下载
  • 作者:Vida Dujmović ; Joachim Gudmundsson ; Pat Morin
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2011
  • 卷号:2011
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    A geometric graph G is an a angle crossing (alpha AC) graph if every pair of crossing edges in G cross at an angle of at least alpha. The concept of right angle crossing (RAC) graphs alpha = pi/2) was recently introduced by Didimo et al. [10]. It was shown that any RAC graph with n vertices has at most 4n-10 edges and that there are infinitely many values of n for which there exists a RAC graph with n vertices and 4n-10 edges. In this paper, we give upper and lower bounds for the number of edges in alphaAC graphs for all 0 < alpha < pi/2.

国家哲学社会科学文献中心版权所有