首页    期刊浏览 2024年11月27日 星期三
登录注册

文章基本信息

  • 标题:Drawing Graphs with Circular Arcs and Right-Angle Crossings
  • 本地全文:下载
  • 作者:Steven Chaplick ; Henry F{"o}rster ; Myroslav Kryven
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:162
  • 页码:21:1-21:14
  • DOI:10.4230/LIPIcs.SWAT.2020.21
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:In a RAC drawing of a graph, vertices are represented by points in the plane, adjacent vertices are connected by line segments, and crossings must form right angles. Graphs that admit such drawings are RAC graphs. RAC graphs are beyond-planar graphs and have been studied extensively. In particular, it is known that a RAC graph with n vertices has at most 4n-10 edges. We introduce a superclass of RAC graphs, which we call arc-RAC graphs. A graph is arc-RAC if it admits a drawing where edges are represented by circular arcs and crossings form right angles. We provide a Turán-type result showing that an arc-RAC graph with n vertices has at most 14n-12 edges and that there are n-vertex arc-RAC graphs with 4.5n - O(â^Sn) edges.
  • 关键词:circular arcs; right-angle crossings; edge density; charging argument
国家哲学社会科学文献中心版权所有