文章基本信息

标题：Coloring Curves That Cross a Fixed Curve
本地全文：下载
作者：Alexandre Rok ; Bartosz Walczak
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：77
页码：56:1-56:15
DOI：10.4230/LIPIcs.SoCG.2017.56
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We prove that for every integer t greater than or equal to 1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is chi-bounded. This is essentially the strongest chi-boundedness result one can get for this kind of graph classes. As a corollary, we prove that for any fixed integers k > 1 and t > 0, every k-quasi-planar topological graph on n vertices with any two edges crossing at most t times has O(n log n) edges.
关键词：String graphs; chi-boundedness; k-quasi-planar graphs