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

文章基本信息

  • 标题:Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c <= 12
  • 本地全文:下载
  • 作者:Drago Bokal ; Zdenek Dvor{'a}k ; Petr Hlinen{'y
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:129
  • 页码:1-15
  • DOI:10.4230/LIPIcs.SoCG.2019.14
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c >= 13 and d >= 1, we give first explicit constructions of c-crossing-critical graphs containing a vertex of degree greater than d. We also show that such unbounded degree constructions do not exist for c <=12, precisely, that there exists a constant D such that every c-crossing-critical graph with c <=12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvorák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <=12.
  • 关键词:graph drawing; crossing number; crossing-critical; zip product
国家哲学社会科学文献中心版权所有