文章基本信息

标题：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