[{"abstract":[{"text":"Van der Holst and Pendavingh introduced a graph parameter σ, which coincides with the more famous Colin de Verdière graph parameter μ for small values. However, the definition of a is much more geometric/topological directly reflecting embeddability properties of the graph. They proved μ(G) ≤ σ(G) + 2 and conjectured σ(G) ≤ σ(G) for any graph G. We confirm this conjecture. As far as we know, this is the first topological upper bound on σ(G) which is, in general, tight.\r\nEquality between μ and σ does not hold in general as van der Holst and Pendavingh showed that there is a graph G with μ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears at much smaller values, namely, we exhibit a graph H for which μ(H) ≥ 7 and σ(H) ≥ 8. We also prove that, in general, the gap can be large: The incidence graphs Hq of finite projective planes of order q satisfy μ(Hq) ∈ O(q3/2) and σ(Hq) ≥ q2.","lang":"eng"}],"author":[{"full_name":"Kaluza, Vojtech","last_name":"Kaluza","orcid":"0000-0002-2512-8698","first_name":"Vojtech","id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","full_name":"Tancer, Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714"}],"publication_status":"published","citation":{"mla":"Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number and Representations of Graphs.” <i>Combinatorica</i>, vol. 42, Springer Nature, 2022, pp. 1317–45, doi:<a href=\"https://doi.org/10.1007/s00493-021-4443-7\">10.1007/s00493-021-4443-7</a>.","ama":"Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations of graphs. <i>Combinatorica</i>. 2022;42:1317-1345. doi:<a href=\"https://doi.org/10.1007/s00493-021-4443-7\">10.1007/s00493-021-4443-7</a>","ista":"Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations of graphs. Combinatorica. 42, 1317–1345.","short":"V. Kaluza, M. Tancer, Combinatorica 42 (2022) 1317–1345.","ieee":"V. Kaluza and M. Tancer, “Even maps, the Colin de Verdière number and representations of graphs,” <i>Combinatorica</i>, vol. 42. Springer Nature, pp. 1317–1345, 2022.","apa":"Kaluza, V., &#38; Tancer, M. (2022). Even maps, the Colin de Verdière number and representations of graphs. <i>Combinatorica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00493-021-4443-7\">https://doi.org/10.1007/s00493-021-4443-7</a>","chicago":"Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number and Representations of Graphs.” <i>Combinatorica</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00493-021-4443-7\">https://doi.org/10.1007/s00493-021-4443-7</a>."},"_id":"10335","publication_identifier":{"issn":["0209-9683"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","acknowledgement":"V. K. gratefully acknowledges the support of Austrian Science Fund (FWF): P 30902-N35. This work was done mostly while he was employed at the University of Innsbruck. During the early stage of this research, V. K. was partially supported by Charles University project GAUK 926416. M. T. is supported by the grant no. 19-04113Y of the Czech Science Foundation(GA ˇCR) and partially supported by Charles University project UNCE/SCI/004.","quality_controlled":"1","oa_version":"Preprint","arxiv":1,"volume":42,"oa":1,"date_updated":"2023-08-02T06:43:27Z","article_processing_charge":"No","title":"Even maps, the Colin de Verdière number and representations of graphs","external_id":{"arxiv":["1907.05055"],"isi":["000798210100003"]},"doi":"10.1007/s00493-021-4443-7","year":"2022","ddc":["514","516"],"isi":1,"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.1907.05055"}],"intvolume":"        42","status":"public","day":"01","type":"journal_article","publication":"Combinatorica","page":"1317-1345","publisher":"Springer Nature","scopus_import":"1","language":[{"iso":"eng"}],"month":"12","article_type":"original","date_published":"2022-12-01T00:00:00Z","date_created":"2021-11-25T13:49:16Z","department":[{"_id":"UlWa"}]},{"publication_status":"published","citation":{"ista":"Kwan MA, Letzter S, Sudakov B, Tran T. 2020. Dense induced bipartite subgraphs in triangle-free graphs. Combinatorica. 40(2), 283–305.","short":"M.A. Kwan, S. Letzter, B. Sudakov, T. Tran, Combinatorica 40 (2020) 283–305.","mla":"Kwan, Matthew Alan, et al. “Dense Induced Bipartite Subgraphs in Triangle-Free Graphs.” <i>Combinatorica</i>, vol. 40, no. 2, Springer, 2020, pp. 283–305, doi:<a href=\"https://doi.org/10.1007/s00493-019-4086-0\">10.1007/s00493-019-4086-0</a>.","ama":"Kwan MA, Letzter S, Sudakov B, Tran T. Dense induced bipartite subgraphs in triangle-free graphs. <i>Combinatorica</i>. 2020;40(2):283-305. doi:<a href=\"https://doi.org/10.1007/s00493-019-4086-0\">10.1007/s00493-019-4086-0</a>","chicago":"Kwan, Matthew Alan, Shoham Letzter, Benny Sudakov, and Tuan Tran. “Dense Induced Bipartite Subgraphs in Triangle-Free Graphs.” <i>Combinatorica</i>. Springer, 2020. <a href=\"https://doi.org/10.1007/s00493-019-4086-0\">https://doi.org/10.1007/s00493-019-4086-0</a>.","ieee":"M. A. Kwan, S. Letzter, B. Sudakov, and T. Tran, “Dense induced bipartite subgraphs in triangle-free graphs,” <i>Combinatorica</i>, vol. 40, no. 2. Springer, pp. 283–305, 2020.","apa":"Kwan, M. A., Letzter, S., Sudakov, B., &#38; Tran, T. (2020). Dense induced bipartite subgraphs in triangle-free graphs. <i>Combinatorica</i>. Springer. <a href=\"https://doi.org/10.1007/s00493-019-4086-0\">https://doi.org/10.1007/s00493-019-4086-0</a>"},"author":[{"orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","last_name":"Kwan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"first_name":"Shoham","full_name":"Letzter, Shoham","last_name":"Letzter"},{"first_name":"Benny","last_name":"Sudakov","full_name":"Sudakov, Benny"},{"last_name":"Tran","full_name":"Tran, Tuan","first_name":"Tuan"}],"abstract":[{"lang":"eng","text":"The problem of finding dense induced bipartite subgraphs in H-free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. In this paper, we obtain several results in this direction. First we prove that any H-free graph with minimum degree at least d contains an induced bipartite subgraph of minimum degree at least cH log d/log log d, thus nearly confirming one and proving another conjecture of Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdœs, Janson, Łuczak and Spencer."}],"oa":1,"date_updated":"2023-02-23T14:01:45Z","volume":40,"article_processing_charge":"No","arxiv":1,"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","quality_controlled":"1","oa_version":"Preprint","_id":"9582","extern":"1","publication_identifier":{"eissn":["1439-6912"],"issn":["0209-9683"]},"doi":"10.1007/s00493-019-4086-0","year":"2020","title":"Dense induced bipartite subgraphs in triangle-free graphs","external_id":{"arxiv":["1810.12144"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1810.12144"}],"type":"journal_article","day":"01","status":"public","intvolume":"        40","page":"283-305","issue":"2","publication":"Combinatorica","article_type":"original","date_published":"2020-04-01T00:00:00Z","month":"04","language":[{"iso":"eng"}],"publisher":"Springer","scopus_import":"1","date_created":"2021-06-22T06:42:26Z"},{"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek","first_name":"Radoslav"},{"full_name":"Kynčl, Jan","last_name":"Kynčl","first_name":"Jan"}],"abstract":[{"lang":"eng","text":"We find a graph of genus 5 and its drawing on the orientable surface of genus 4 with every pair of independent edges crossing an even number of times. This shows that the strong Hanani–Tutte theorem cannot be extended to the orientable surface of genus 4. As a base step in the construction we use a counterexample to an extension of the unified Hanani–Tutte theorem on the torus."}],"publication_status":"published","citation":{"ama":"Fulek R, Kynčl J. Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. <i>Combinatorica</i>. 2019;39(6):1267-1279. doi:<a href=\"https://doi.org/10.1007/s00493-019-3905-7\">10.1007/s00493-019-3905-7</a>","mla":"Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte Theorem on the Surface of Genus 4.” <i>Combinatorica</i>, vol. 39, no. 6, Springer Nature, 2019, pp. 1267–79, doi:<a href=\"https://doi.org/10.1007/s00493-019-3905-7\">10.1007/s00493-019-3905-7</a>.","short":"R. Fulek, J. Kynčl, Combinatorica 39 (2019) 1267–1279.","ista":"Fulek R, Kynčl J. 2019. Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. Combinatorica. 39(6), 1267–1279.","ieee":"R. Fulek and J. Kynčl, “Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4,” <i>Combinatorica</i>, vol. 39, no. 6. Springer Nature, pp. 1267–1279, 2019.","apa":"Fulek, R., &#38; Kynčl, J. (2019). Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. <i>Combinatorica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00493-019-3905-7\">https://doi.org/10.1007/s00493-019-3905-7</a>","chicago":"Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte Theorem on the Surface of Genus 4.” <i>Combinatorica</i>. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/s00493-019-3905-7\">https://doi.org/10.1007/s00493-019-3905-7</a>."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","quality_controlled":"1","oa_version":"Preprint","project":[{"grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme"},{"_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","grant_number":"M02281"}],"_id":"7034","publication_identifier":{"issn":["0209-9683"],"eissn":["1439-6912"]},"date_updated":"2023-08-30T07:26:25Z","oa":1,"volume":39,"article_processing_charge":"No","arxiv":1,"title":"Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4","external_id":{"arxiv":["1709.00508"],"isi":["000493267200003"]},"ec_funded":1,"year":"2019","doi":"10.1007/s00493-019-3905-7","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.00508"}],"isi":1,"status":"public","intvolume":"        39","type":"journal_article","day":"29","page":"1267-1279","issue":"6","publication":"Combinatorica","language":[{"iso":"eng"}],"publisher":"Springer Nature","scopus_import":"1","date_published":"2019-10-29T00:00:00Z","article_type":"original","month":"10","date_created":"2019-11-18T14:29:50Z","department":[{"_id":"UlWa"}]},{"doi":"10.1007/BF01285815","year":"1992","title":"The number of edges of many faces in a line segment arrangement","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF01285815"}],"citation":{"ama":"Aronov B, Edelsbrunner H, Guibas L, Sharir M. The number of edges of many faces in a line segment arrangement. <i>Combinatorica</i>. 1992;12(3):261-274. doi:<a href=\"https://doi.org/10.1007/BF01285815\">10.1007/BF01285815</a>","mla":"Aronov, Boris, et al. “The Number of Edges of Many Faces in a Line Segment Arrangement.” <i>Combinatorica</i>, vol. 12, no. 3, Springer, 1992, pp. 261–74, doi:<a href=\"https://doi.org/10.1007/BF01285815\">10.1007/BF01285815</a>.","ista":"Aronov B, Edelsbrunner H, Guibas L, Sharir M. 1992. The number of edges of many faces in a line segment arrangement. Combinatorica. 12(3), 261–274.","short":"B. Aronov, H. Edelsbrunner, L. Guibas, M. Sharir, Combinatorica 12 (1992) 261–274.","ieee":"B. Aronov, H. Edelsbrunner, L. Guibas, and M. Sharir, “The number of edges of many faces in a line segment arrangement,” <i>Combinatorica</i>, vol. 12, no. 3. Springer, pp. 261–274, 1992.","apa":"Aronov, B., Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1992). The number of edges of many faces in a line segment arrangement. <i>Combinatorica</i>. Springer. <a href=\"https://doi.org/10.1007/BF01285815\">https://doi.org/10.1007/BF01285815</a>","chicago":"Aronov, Boris, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. “The Number of Edges of Many Faces in a Line Segment Arrangement.” <i>Combinatorica</i>. Springer, 1992. <a href=\"https://doi.org/10.1007/BF01285815\">https://doi.org/10.1007/BF01285815</a>."},"publication_status":"published","abstract":[{"text":"We show that the maximum number of edges bounding m faces in an arrangement of n line segments in the plane is O(m2/3n2/3+nα(n)+nlog m). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is Ω(m2/3n2/3+nα(n)). In addition, we show that the number of edges bounding any m faces in an arrangement of n line segments with a total of t intersecting pairs is O(m2/3t1/3+nα(t/n)+nmin{log m,log t/n}), almost matching the lower bound of Ω(m2/3t1/3+nα(t/n)) demonstrated in this paper.","lang":"eng"}],"author":[{"full_name":"Aronov, Boris","last_name":"Aronov","first_name":"Boris"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"}],"article_processing_charge":"No","publist_id":"2074","date_updated":"2022-03-15T15:44:26Z","volume":12,"extern":"1","publication_identifier":{"issn":["0209-9683"]},"_id":"4053","oa_version":"None","quality_controlled":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","month":"09","article_type":"original","date_published":"1992-09-01T00:00:00Z","scopus_import":"1","publisher":"Springer","language":[{"iso":"eng"}],"date_created":"2018-12-11T12:06:40Z","day":"01","type":"journal_article","intvolume":"        12","status":"public","publication":"Combinatorica","issue":"3","page":"261 - 274"},{"date_created":"2018-12-11T12:06:45Z","scopus_import":"1","publisher":"Springer","language":[{"iso":"eng"}],"month":"09","article_type":"original","date_published":"1990-09-01T00:00:00Z","publication":"Combinatorica","issue":"3","page":"251 - 260","intvolume":"        10","status":"public","day":"01","type":"journal_article","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02122779"}],"title":"An acyclicity theorem for cell complexes in d dimension","year":"1990","doi":"10.1007/BF02122779","extern":"1","publication_identifier":{"eissn":["1439-6912"],"issn":["0209-9683"]},"_id":"4069","quality_controlled":"1","oa_version":"None","acknowledgement":"Research reported in this paper was supported by the National Science Foundation under grant CCR-8714565.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","article_processing_charge":"No","publist_id":"2050","date_updated":"2022-02-21T11:08:30Z","volume":10,"abstract":[{"lang":"eng","text":"Let C be a cell complex in d-dimensional Euclidean space whose faces are obtained by orthogonal projection of the faces of a convex polytope in d + 1 dimensions. For example, the Delaunay triangulation of a finite point set is such a cell complex. This paper shows that the in front/behind relation defined for the faces of C with respect to any fixed viewpoint x is acyclic. This result has applications to hidden line/surface removal and other problems in computational geometry."}],"author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert"}],"citation":{"mla":"Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.” <i>Combinatorica</i>, vol. 10, no. 3, Springer, 1990, pp. 251–60, doi:<a href=\"https://doi.org/10.1007/BF02122779\">10.1007/BF02122779</a>.","ama":"Edelsbrunner H. An acyclicity theorem for cell complexes in d dimension. <i>Combinatorica</i>. 1990;10(3):251-260. doi:<a href=\"https://doi.org/10.1007/BF02122779\">10.1007/BF02122779</a>","short":"H. Edelsbrunner, Combinatorica 10 (1990) 251–260.","ista":"Edelsbrunner H. 1990. An acyclicity theorem for cell complexes in d dimension. Combinatorica. 10(3), 251–260.","ieee":"H. Edelsbrunner, “An acyclicity theorem for cell complexes in d dimension,” <i>Combinatorica</i>, vol. 10, no. 3. Springer, pp. 251–260, 1990.","apa":"Edelsbrunner, H. (1990). An acyclicity theorem for cell complexes in d dimension. <i>Combinatorica</i>. Springer. <a href=\"https://doi.org/10.1007/BF02122779\">https://doi.org/10.1007/BF02122779</a>","chicago":"Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.” <i>Combinatorica</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02122779\">https://doi.org/10.1007/BF02122779</a>."},"publication_status":"published"}]