Abstract
An r-quasiplanar graph is a graph drawn in the plane with no r pairwise crossing edges. Let \(s \ge 3\) be an integer and \(r=2^s\). We prove that there is a constant C such that every r-quasiplanar graph with \(n \ge r\) vertices has at most \(n\left( Cs^{-1}\log n\right) ^{2s-4}\) edges.
A graph whose vertices are continuous curves in the plane, two being connected by an edge if and only if they intersect, is called a string graph. We show that for every \(\epsilon >0\), there exists \(\delta >0\) such that every string graph with n vertices, whose chromatic number is at least \(n^{\epsilon }\) contains a clique of size at least \(n^{\delta }\). A clique of this size or a coloring using fewer than \(n^{\epsilon }\) colors can be found by a polynomial time algorithm in terms of the size of the geometric representation of the set of strings.
In the process, we use, generalize, and strengthen previous results of Lee, Tomon, and others. All of our theorems are related to geometric variants of the following classical graph-theoretic problem of Erdős, Gallai, and Rogers. Given a \(K_r\)-free graph on n vertices and an integer \(s<r\), at least how many vertices can we find such that the subgraph induced by them is \(K_s\)-free?
J. Fox—Supported by a Packard Fellowship and by NSF award DMS-1855635.
J. Pach—Supported by NKFIH grants K-131529, Austrian Science Fund Z 342-N31, and ERC Advanced Grant “GeoScape.”
A. Suk—Supported by an NSF CAREER award and NSF award DMS-1952786.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ackerman, E.: On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discrete Comput. Geom. 41, 365–375 (2009)
Ackerman, E.: Quasi-planar graphs. In: Hong, S.-H., Tokuyama, T. (eds.) Beyond Planar Graphs, pp. 31–45. Springer, Singapore (2020). https://doi.org/10.1007/978-981-15-6533-5_3
Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. J. Comb. Theory, Ser. A 114(3), 563–571 (2007)
Agarwal, P., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear number of edges. Combinatorica 17, 1–9 (1997)
Brass, P., Moser, W.O.J., Pach, J.: Research problems in discrete geometry. Springer (2005)
Burling, J.: On coloring problems of families of polytopes. (Ph.D. thesis), University of Colorado, Boulder 1(5) (1965)
Davies, J., McCarty, R.: Circle graphs are quadratically \(\chi \) -bounded. Bull. London Math. Soc. 53, 673–679 (2021)
Davis, J.: Improved bounds for colouring circle graphs. Preprint, arXiv:2107.03585 (2021)
Dudek, A., Retter, T., Rödl, V.: On generalized ramsey numbers of erdos and rogers. J. Combin. Theory Ser. B 109, 213–227 (2014)
Dudek, A., Rödl, V.: On \(k_s\)-free subgraphs in \(k_{s+k}\)-free graphs and vertex folkman numbers. Combinatorica 31, 39–53 (2011)
Erdős, P., Gallai, T.: On the minimal number of vertices representing the edges of a graph. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6, 181–203 (1961)
Erdős, P., Rogers, C.A.: The construction of certain graphs. Canad. J. Math. 14, 702–707 (1962)
Fox, J., Pach, J.: Separator theorems and turán-type results for planar intersection graphs. Adv. Math. 219, 1070–1080 (2008)
Fox, J., Pach, J.: A separator theorem for string graphs and its applications. Combin. Probab. Comput. 19, 371–390 (2010)
Fox, J., Pach, J.: Coloring \(k_k\)-free intersection graphs of geometric objects in the plane. European J. Combin. 33, 853–866 (2012)
Fox, J., Pach, J.: String graphs and incomparability graphs. Adv. Math. 230, 1381–1401 (2012)
Fox, J., Pach, J.: Applications of a new separator theorem for string graphs. Combin. Probab. Comput. 23, 66–74 (2014)
Gyárfás, A.: On the chromatic number of multiple interval graphs and overlap graphs. Discrete Math. 55, 161–166 (1985)
Janzer, O., Gowers, W.T.: Improved bounds for the erdos-rogers function. Adv. Comb. 3, 1–27 (2020)
Kostochka, A.: O verkhnikh otsenkakh khromaticheskogo chisla grafov (on upper bounds for the chromatic number of graphs). In: Dementyev, V.T. (ed.) Modeli i metody optimizacii, Akad. Nauk SSSR SO 10, pp. 204–226 (1988)
Kostochka, A., Kratochvíl, J.: Covering and coloring polygon-circle graphs. Discrete Math. 163, 299–305 (1997)
Krivelevich, M.: \(k_s\)-free graphs without large \(k_r\)-free subgraphs. Combin. Probab. Comput. 3, 349–354 (1994)
Krivelevich, M.: Bounding ramsey numbers through large deviation inequalities. Random Struct. Algorithms 7, 145–155 (1995)
Lee, J.: Separators in region intersection graphs. ITCS 7, 1:1–1:8 (2017). Full version: arXiv:1608.01612
Lipton, R., Rose, D., Tarjan, R.: Generalized nested dissections. SIAM J. Numer. Anal. 16, 346–358 (1979)
McGuinness, S.: Colouring arcwise connected sets in the plane, i. Graphs Combin. 16, 429–439 (2000)
Pach, J., Radoičić, R., Tóth, G.: Relaxing planarity for topological graphs. In: Akiyama, J., Kano, M. (eds.) JCDCG 2002. LNCS, vol. 2866, pp. 221–232. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-44400-8_24
Pawlik, A., Kozik, J., Krawczyk, T., Lasoń, M., Micek, P., Trotter, W., Walczak, B.: Triangle-free intersection graphs of line segments with large chromatic number. J. Combin. Theory Ser. B 105, 6–10 (2014)
Rok, A., Walczak, B.: Coloring curves that cross a fixed curve. Discrete Comput. Geom. 61, 830–851 (2019)
Rok, A., Walczak, B.: Outerstring graphs are \(\chi \)-bounded. SIAM J. Discrete Math. 13, 2181–2199 (2019)
Sudakov, B.: Large \(k_r\)-free subgraphs in \(k_s\)-free graphs and some other ramsey-type problems. Random Struct. Algorithms 26, 253–265 (2005)
Suk, A.: Coloring intersection graphs of \(x\)-monotone curves in the plane. Combinatorica 34, 487–505 (2014)
Tomon, I.: String graphs have the erdos-hajnal property. arXiv preprint. arXiv:2002.10350 (2020)
Valtr, P.: On geometric graphs with no \(k\) pairwise parallel edges. Discrete Comput. Geom. 19, 461–469 (1998)
Walczak, B.: Triangle-free geometric intersection graphs with no large independent sets. Discrete Comput. Geom. 53, 221–225 (2015)
Wolfovitz, G.: \(k_4\)-free graphs without large induced triangle-free subgraphs. Combinatorica 33, 623–631 (2013)
Acknowledgement
We are grateful to Zach Hunter for carefully reading our manuscript and pointing out several mistakes.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Fox, J., Pach, J., Suk, A. (2023). Quasiplanar Graphs, String Graphs, and the Erdős-Gallai Problem. In: Angelini, P., von Hanxleden, R. (eds) Graph Drawing and Network Visualization. GD 2022. Lecture Notes in Computer Science, vol 13764. Springer, Cham. https://doi.org/10.1007/978-3-031-22203-0_16
Download citation
DOI: https://doi.org/10.1007/978-3-031-22203-0_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22202-3
Online ISBN: 978-3-031-22203-0
eBook Packages: Computer ScienceComputer Science (R0)