[{"isi":1,"day":"27","department":[{"_id":"UlWa"}],"quality_controlled":"1","arxiv":1,"oa":1,"publisher":"Springer Nature","status":"public","date_created":"2023-08-06T22:01:12Z","abstract":[{"lang":"eng","text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common point. In this paper, we prove a trengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result generalizes to a result about simplices in Rd, d≥2."}],"_id":"13974","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"epub_ahead","external_id":{"isi":["001038546500001"],"arxiv":["1812.04911"]},"author":[{"last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"last_name":"Gärtner","first_name":"Bernd","full_name":"Gärtner, Bernd"},{"last_name":"Kupavskii","first_name":"Andrey","full_name":"Kupavskii, Andrey"},{"full_name":"Valtr, Pavel","first_name":"Pavel","last_name":"Valtr"},{"orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"M02281"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"acknowledgement":"Part of the research leading to this paper was done during the 16th Gremo Workshop on Open Problems (GWOP), Waltensburg, Switzerland, June 12–16, 2018. We thank Patrick Schnider for suggesting the problem, and Stefan Felsner, Malte Milatz, and Emo Welzl for fruitful discussions during the workshop. We also thank Stefan Felsner and Manfred Scheucher for finding, communicating the example from Sect. 3.3, and the kind permission to include their visualization of the point set. We thank Dömötör Pálvölgyi, the SoCG reviewers, and DCG reviewers for various helpful comments.\r\nR. Fulek gratefully acknowledges support from Austrian Science Fund (FWF), Project  M2281-N35. A. Kupavskii was supported by the Advanced Postdoc.Mobility Grant no. P300P2_177839 of the Swiss National Science Foundation. Research by P. Valtr was supported by the Grant no. 18-19158 S of the Czech Science Foundation (GAČR).","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1812.04911"}],"title":"The crossing Tverberg theorem","article_processing_charge":"No","publication":"Discrete and Computational Geometry","year":"2023","language":[{"iso":"eng"}],"date_updated":"2023-12-13T12:03:35Z","citation":{"chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-023-00532-x\">https://doi.org/10.1007/s00454-023-00532-x</a>.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2023. The crossing Tverberg theorem. Discrete and Computational Geometry.","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational Geometry (2023).","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., &#38; Wagner, U. (2023). The crossing Tverberg theorem. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-023-00532-x\">https://doi.org/10.1007/s00454-023-00532-x</a>","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” <i>Discrete and Computational Geometry</i>, Springer Nature, 2023, doi:<a href=\"https://doi.org/10.1007/s00454-023-00532-x\">10.1007/s00454-023-00532-x</a>.","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023.","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. <i>Discrete and Computational Geometry</i>. 2023. doi:<a href=\"https://doi.org/10.1007/s00454-023-00532-x\">10.1007/s00454-023-00532-x</a>"},"type":"journal_article","month":"07","date_published":"2023-07-27T00:00:00Z","scopus_import":"1","related_material":{"record":[{"id":"6647","relation":"earlier_version","status":"public"}]},"article_type":"original","doi":"10.1007/s00454-023-00532-x","oa_version":"Preprint"},{"external_id":{"isi":["000825014500001"],"arxiv":["1803.05085"]},"author":[{"last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"first_name":"Jan","last_name":"Kynčl","full_name":"Kynčl, Jan"}],"project":[{"call_identifier":"FWF","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"volume":68,"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"abstract":[{"lang":"eng","text":"A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z2 -genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t×t grid or one of the following so-called t -Kuratowski graphs: K3,t, or t copies of K5 or K3,3 sharing at most two common vertices. We show that the Z2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its Z2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani–Tutte theorem on orientable surfaces. We also obtain an analogous result for Euler genus and Euler Z2-genus of graphs."}],"_id":"11593","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","publisher":"Springer Nature","page":"425-447","status":"public","date_created":"2022-07-17T22:01:56Z","isi":1,"day":"01","department":[{"_id":"UlWa"}],"quality_controlled":"1","arxiv":1,"oa":1,"related_material":{"record":[{"id":"186","relation":"earlier_version","status":"public"}]},"doi":"10.1007/s00454-022-00412-w","article_type":"original","oa_version":"Preprint","citation":{"mla":"Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” <i>Discrete and Computational Geometry</i>, vol. 68, Springer Nature, 2022, pp. 425–47, doi:<a href=\"https://doi.org/10.1007/s00454-022-00412-w\">10.1007/s00454-022-00412-w</a>.","ieee":"R. Fulek and J. Kynčl, “The Z2-Genus of Kuratowski minors,” <i>Discrete and Computational Geometry</i>, vol. 68. Springer Nature, pp. 425–447, 2022.","ama":"Fulek R, Kynčl J. The Z2-Genus of Kuratowski minors. <i>Discrete and Computational Geometry</i>. 2022;68:425-447. doi:<a href=\"https://doi.org/10.1007/s00454-022-00412-w\">10.1007/s00454-022-00412-w</a>","chicago":"Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00454-022-00412-w\">https://doi.org/10.1007/s00454-022-00412-w</a>.","ista":"Fulek R, Kynčl J. 2022. The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. 68, 425–447.","short":"R. Fulek, J. Kynčl, Discrete and Computational Geometry 68 (2022) 425–447.","apa":"Fulek, R., &#38; Kynčl, J. (2022). The Z2-Genus of Kuratowski minors. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00412-w\">https://doi.org/10.1007/s00454-022-00412-w</a>"},"date_updated":"2023-08-14T12:43:52Z","type":"journal_article","date_published":"2022-09-01T00:00:00Z","month":"09","scopus_import":"1","article_processing_charge":"No","publication":"Discrete and Computational Geometry","year":"2022","language":[{"iso":"eng"}],"acknowledgement":"We thank Zdeněk Dvořák, Xavier Goaoc, and Pavel Paták for helpful discussions. We also thank Bojan Mohar, Paul Seymour, Gelasio Salazar, Jim Geelen, and John Maharry for information about their unpublished results related to Conjecture 3.1. Finally we thank the reviewers for corrections and suggestions for improving the presentation.\r\nSupported by Austrian Science Fund (FWF): M2281-N35. Supported by project 19-04113Y of the Czech Science Foundation (GAČR), by the Czech-French collaboration project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM), and by Charles University project UNCE/SCI/004.","intvolume":"        68","title":"The Z2-Genus of Kuratowski minors","main_file_link":[{"url":"https://arxiv.org/abs/1803.05085","open_access":"1"}]},{"abstract":[{"text":"A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is [Formula presented](n−1), and that this bound is best possible for infinitely many values of n.","lang":"eng"}],"_id":"5857","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","external_id":{"arxiv":["1708.08037"],"isi":["000466061100020"]},"author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pach, János","first_name":"János","last_name":"Pach"}],"project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF"}],"volume":259,"publication_identifier":{"issn":["0166218X"]},"isi":1,"day":"30","department":[{"_id":"UlWa"}],"quality_controlled":"1","arxiv":1,"issue":"4","oa":1,"page":"266-231","publisher":"Elsevier","status":"public","date_created":"2019-01-20T22:59:17Z","citation":{"chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” <i>Discrete Applied Mathematics</i>. Elsevier, 2019. <a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">https://doi.org/10.1016/j.dam.2018.12.025</a>.","ista":"Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied Mathematics. 259(4), 266–231.","short":"R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.","apa":"Fulek, R., &#38; Pach, J. (2019). Thrackles: An improved upper bound. <i>Discrete Applied Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">https://doi.org/10.1016/j.dam.2018.12.025</a>","mla":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” <i>Discrete Applied Mathematics</i>, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:<a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">10.1016/j.dam.2018.12.025</a>.","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” <i>Discrete Applied Mathematics</i>, vol. 259, no. 4. Elsevier, pp. 266–231, 2019.","ama":"Fulek R, Pach J. Thrackles: An improved upper bound. <i>Discrete Applied Mathematics</i>. 2019;259(4):266-231. doi:<a href=\"https://doi.org/10.1016/j.dam.2018.12.025\">10.1016/j.dam.2018.12.025</a>"},"date_updated":"2023-08-24T14:39:33Z","type":"journal_article","month":"04","date_published":"2019-04-30T00:00:00Z","scopus_import":"1","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"433"}]},"doi":"10.1016/j.dam.2018.12.025","article_type":"original","oa_version":"Preprint","intvolume":"       259","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.08037"}],"title":"Thrackles: An improved upper bound","article_processing_charge":"No","publication":"Discrete Applied Mathematics","language":[{"iso":"eng"}],"year":"2019"},{"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6647","abstract":[{"text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.","lang":"eng"}],"publication_identifier":{"isbn":["9783959771047"],"issn":["1868-8969"]},"volume":129,"project":[{"grant_number":"M02281","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"external_id":{"arxiv":["1812.04911"]},"author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Gärtner, Bernd","first_name":"Bernd","last_name":"Gärtner"},{"full_name":"Kupavskii, Andrey","last_name":"Kupavskii","first_name":"Andrey"},{"last_name":"Valtr","first_name":"Pavel","full_name":"Valtr, Pavel"},{"first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"oa":1,"arxiv":1,"quality_controlled":"1","department":[{"_id":"UlWa"}],"day":"01","date_created":"2019-07-17T10:35:04Z","status":"public","page":"38:1-38:13","file":[{"date_updated":"2020-07-14T12:47:35Z","creator":"dernst","file_size":559837,"content_type":"application/pdf","relation":"main_file","file_id":"6667","file_name":"2019_LIPICS_Fulek.pdf","access_level":"open_access","checksum":"d6d017f8b41291b94d102294fa96ae9c","date_created":"2019-07-24T06:54:52Z"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","scopus_import":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["000","510"],"date_published":"2019-06-01T00:00:00Z","month":"06","type":"conference","has_accepted_license":"1","citation":{"short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., &#38; Wagner, U. (2019). The crossing Tverberg theorem. In <i>35th International Symposium on Computational Geometry</i> (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">https://doi.org/10.4230/LIPICS.SOCG.2019.38</a>","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” In <i>35th International Symposium on Computational Geometry</i>, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">https://doi.org/10.4230/LIPICS.SOCG.2019.38</a>.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: <i>35th International Symposium on Computational Geometry</i>. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">10.4230/LIPICS.SOCG.2019.38</a>","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” <i>35th International Symposium on Computational Geometry</i>, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13, doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">10.4230/LIPICS.SOCG.2019.38</a>.","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in <i>35th International Symposium on Computational Geometry</i>, Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13."},"date_updated":"2023-12-13T12:03:35Z","file_date_updated":"2020-07-14T12:47:35Z","oa_version":"Published Version","conference":{"start_date":"2019-06-18","name":"SoCG 2019: Symposium on Computational Geometry","end_date":"2019-06-21","location":"Portland, OR, United States"},"doi":"10.4230/LIPICS.SOCG.2019.38","related_material":{"record":[{"relation":"later_version","id":"13974","status":"public"}]},"alternative_title":["LIPIcs"],"title":"The crossing Tverberg theorem","intvolume":"       129","year":"2019","language":[{"iso":"eng"}],"publication":"35th International Symposium on Computational Geometry"},{"publication":"ACM Transactions on Algorithms","language":[{"iso":"eng"}],"year":"2019","main_file_link":[{"url":"https://arxiv.org/abs/1709.09209","open_access":"1"}],"title":"Recognizing weak embeddings of graphs","intvolume":"        15","article_type":"original","doi":"10.1145/3344549","related_material":{"record":[{"id":"309","relation":"earlier_version","status":"public"}]},"oa_version":"Preprint","article_number":"50","type":"journal_article","date_updated":"2023-09-15T12:19:31Z","citation":{"ista":"Akitaya H, Fulek R, Tóth C. 2019. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 15(4), 50.","chicago":"Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs.” <i>ACM Transactions on Algorithms</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3344549\">https://doi.org/10.1145/3344549</a>.","apa":"Akitaya, H., Fulek, R., &#38; Tóth, C. (2019). Recognizing weak embeddings of graphs. <i>ACM Transactions on Algorithms</i>. ACM. <a href=\"https://doi.org/10.1145/3344549\">https://doi.org/10.1145/3344549</a>","short":"H. Akitaya, R. Fulek, C. Tóth, ACM Transactions on Algorithms 15 (2019).","ieee":"H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” <i>ACM Transactions on Algorithms</i>, vol. 15, no. 4. ACM, 2019.","mla":"Akitaya, Hugo, et al. “Recognizing Weak Embeddings of Graphs.” <i>ACM Transactions on Algorithms</i>, vol. 15, no. 4, 50, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3344549\">10.1145/3344549</a>.","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. <i>ACM Transactions on Algorithms</i>. 2019;15(4). doi:<a href=\"https://doi.org/10.1145/3344549\">10.1145/3344549</a>"},"scopus_import":1,"month":"10","date_published":"2019-10-01T00:00:00Z","publisher":"ACM","date_created":"2019-11-04T15:45:17Z","status":"public","department":[{"_id":"UlWa"}],"day":"01","oa":1,"issue":"4","arxiv":1,"quality_controlled":"1","external_id":{"arxiv":["1709.09209"]},"author":[{"full_name":"Akitaya, Hugo","last_name":"Akitaya","first_name":"Hugo"},{"full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774"},{"last_name":"Tóth","first_name":"Csaba","full_name":"Tóth, Csaba"}],"volume":15,"project":[{"grant_number":"M02281","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"_id":"6982","abstract":[{"lang":"eng","text":"We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ϕ : G → M of a graph G into a 2-manifold M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to the same point or overlapping arcs due to data compression or low resolution. This raises the computational problem of deciding whether a given map ϕ : G → M comes from an embedding. A map ϕ : G → M is a weak embedding if it can be perturbed into an embedding ψ ϵ : G → M with ‖ ϕ − ψ ϵ ‖ < ϵ for every ϵ > 0, where ‖.‖ is the unform norm.\r\nA polynomial-time algorithm for recognizing weak embeddings has recently been found by Fulek and Kynčl. It reduces the problem to solving a system of linear equations over Z2. It runs in O(n2ω)≤ O(n4.75) time, where ω ∈ [2,2.373) is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler: We perform a sequence of local operations that gradually “untangles” the image ϕ(G) into an embedding ψ(G) or reports that ϕ is not a weak embedding. It combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.\r\n"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kynčl, Jan","first_name":"Jan","last_name":"Kynčl"}],"external_id":{"isi":["000493267200003"],"arxiv":["1709.00508"]},"publication_identifier":{"eissn":["1439-6912"],"issn":["0209-9683"]},"volume":39,"project":[{"call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF"}],"_id":"7034","abstract":[{"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.","lang":"eng"}],"publication_status":"published","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Springer Nature","page":"1267-1279","date_created":"2019-11-18T14:29:50Z","status":"public","department":[{"_id":"UlWa"}],"day":"29","isi":1,"oa":1,"issue":"6","arxiv":1,"quality_controlled":"1","ec_funded":1,"article_type":"original","doi":"10.1007/s00493-019-3905-7","oa_version":"Preprint","type":"journal_article","citation":{"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>.","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.","short":"R. Fulek, J. Kynčl, Combinatorica 39 (2019) 1267–1279.","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>","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>.","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.","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>"},"date_updated":"2023-08-30T07:26:25Z","scopus_import":"1","date_published":"2019-10-29T00:00:00Z","month":"10","publication":"Combinatorica","article_processing_charge":"No","year":"2019","language":[{"iso":"eng"}],"title":"Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.00508"}],"intvolume":"        39"},{"month":"06","date_published":"2019-06-01T00:00:00Z","ddc":["000"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"scopus_import":1,"has_accepted_license":"1","date_updated":"2021-01-12T08:13:24Z","citation":{"mla":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>, vol. 129, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">10.4230/LIPICS.SOCG.2019.39</a>.","ieee":"R. Fulek and J. Kyncl, “Z_2-Genus of graphs and minimum rank of partial symmetric matrices,” in <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>, Portland, OR, United States, 2019, vol. 129.","ama":"Fulek R, Kyncl J. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In: <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">10.4230/LIPICS.SOCG.2019.39</a>","chicago":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” In <i>35th International Symposium on Computational Geometry (SoCG 2019)</i>, Vol. 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">https://doi.org/10.4230/LIPICS.SOCG.2019.39</a>.","ista":"Fulek R, Kyncl J. 2019. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. 35th International Symposium on Computational Geometry (SoCG 2019). SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 39.","short":"R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","apa":"Fulek, R., &#38; Kyncl, J. (2019). Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In <i>35th International Symposium on Computational Geometry (SoCG 2019)</i> (Vol. 129). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.39\">https://doi.org/10.4230/LIPICS.SOCG.2019.39</a>"},"type":"conference","article_number":"39","oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:57Z","alternative_title":["LIPIcs"],"conference":{"location":"Portland, OR, United States","name":"SoCG: Symposium on Computational Geometry","start_date":"2019-06-18","end_date":"2019-06-21"},"doi":"10.4230/LIPICS.SOCG.2019.39","intvolume":"       129","title":"Z_2-Genus of graphs and minimum rank of partial symmetric matrices","year":"2019","language":[{"iso":"eng"}],"publication":"35th International Symposium on Computational Geometry (SoCG 2019)","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"text":"The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest. ","lang":"eng"}],"_id":"7401","project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","call_identifier":"FWF"}],"volume":129,"publication_identifier":{"isbn":["978-3-95977-104-7"],"issn":["1868-8969"]},"author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kyncl","first_name":"Jan","full_name":"Kyncl, Jan"}],"external_id":{"arxiv":["1903.08637"]},"quality_controlled":"1","arxiv":1,"oa":1,"day":"01","department":[{"_id":"UlWa"}],"status":"public","date_created":"2020-01-29T16:17:05Z","file":[{"file_id":"7445","relation":"main_file","content_type":"application/pdf","file_size":628347,"date_updated":"2020-07-14T12:47:57Z","creator":"dernst","date_created":"2020-02-04T09:14:31Z","checksum":"aac37b09118cc0ab58cf77129e691f8c","access_level":"open_access","file_name":"2019_LIPIcs_Fulek.pdf"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"day":"01","department":[{"_id":"UlWa"}],"quality_controlled":"1","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"checksum":"f1b94f1a75b37c414a1f61d59fb2cd4c","date_created":"2018-12-17T12:33:52Z","file_name":"2018_LIPIcs_Fulek.pdf","access_level":"open_access","relation":"main_file","file_id":"5701","date_updated":"2020-07-14T12:45:19Z","creator":"dernst","file_size":718857,"content_type":"application/pdf"}],"date_created":"2018-12-11T11:45:04Z","status":"public","abstract":[{"lang":"eng","text":"We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint &quot;pipes&quot; corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once."}],"_id":"185","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav"},{"full_name":"Kynčl, Jan","last_name":"Kynčl","first_name":"Jan"}],"project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"M02281"}],"publication_identifier":{"isbn":["978-3-95977-066-8"]},"volume":99,"title":"Hanani-Tutte for approximating maps of graphs","intvolume":"        99","year":"2018","language":[{"iso":"eng"}],"type":"conference","citation":{"ama":"Fulek R, Kynčl J. Hanani-Tutte for approximating maps of graphs. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">10.4230/LIPIcs.SoCG.2018.39</a>","mla":"Fulek, Radoslav, and Jan Kynčl. <i>Hanani-Tutte for Approximating Maps of Graphs</i>. Vol. 99, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">10.4230/LIPIcs.SoCG.2018.39</a>.","ieee":"R. Fulek and J. Kynčl, “Hanani-Tutte for approximating maps of graphs,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","apa":"Fulek, R., &#38; Kynčl, J. (2018). Hanani-Tutte for approximating maps of graphs (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">https://doi.org/10.4230/LIPIcs.SoCG.2018.39</a>","chicago":"Fulek, Radoslav, and Jan Kynčl. “Hanani-Tutte for Approximating Maps of Graphs,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.39\">https://doi.org/10.4230/LIPIcs.SoCG.2018.39</a>.","ista":"Fulek R, Kynčl J. 2018. Hanani-Tutte for approximating maps of graphs. SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in Information, LIPIcs, vol. 99, 39."},"has_accepted_license":"1","date_updated":"2021-01-12T06:53:36Z","article_number":"39","ddc":["510"],"month":"01","date_published":"2018-01-01T00:00:00Z","scopus_import":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2018-06-11","end_date":"2018-06-14","location":"Budapest, Hungary"},"doi":"10.4230/LIPIcs.SoCG.2018.39","publist_id":"7735","alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"oa_version":"Published Version","file_date_updated":"2020-07-14T12:45:19Z"},{"arxiv":1,"oa":1,"quality_controlled":"1","department":[{"_id":"UlWa"}],"day":"11","status":"public","date_created":"2018-12-11T11:45:05Z","page":"40.1 - 40.14","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","_id":"186","abstract":[{"lang":"eng","text":"A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The ℤ2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t × t grid or one of the following so-called t-Kuratowski graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the ℤ2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its ℤ2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces."}],"volume":99,"project":[{"grant_number":"M02281","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs"}],"author":[{"last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"full_name":"Kynčl, Jan","first_name":"Jan","last_name":"Kynčl"}],"external_id":{"arxiv":["1803.05085"]},"intvolume":"        99","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.05085"}],"title":"The ℤ2-Genus of Kuratowski minors","language":[{"iso":"eng"}],"year":"2018","article_processing_charge":"No","scopus_import":"1","date_published":"2018-06-11T00:00:00Z","month":"06","date_updated":"2023-08-14T12:43:51Z","citation":{"mla":"Fulek, Radoslav, and Jan Kynčl. <i>The ℤ2-Genus of Kuratowski Minors</i>. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">10.4230/LIPIcs.SoCG.2018.40</a>.","ieee":"R. Fulek and J. Kynčl, “The ℤ2-Genus of Kuratowski minors,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99, p. 40.1-40.14.","ama":"Fulek R, Kynčl J. The ℤ2-Genus of Kuratowski minors. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:40.1-40.14. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">10.4230/LIPIcs.SoCG.2018.40</a>","chicago":"Fulek, Radoslav, and Jan Kynčl. “The ℤ2-Genus of Kuratowski Minors,” 99:40.1-40.14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">https://doi.org/10.4230/LIPIcs.SoCG.2018.40</a>.","ista":"Fulek R, Kynčl J. 2018. The ℤ2-Genus of Kuratowski minors. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 40.1-40.14.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14.","apa":"Fulek, R., &#38; Kynčl, J. (2018). The ℤ2-Genus of Kuratowski minors (Vol. 99, p. 40.1-40.14). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.40\">https://doi.org/10.4230/LIPIcs.SoCG.2018.40</a>"},"type":"conference","oa_version":"Submitted Version","alternative_title":["LIPIcs"],"related_material":{"record":[{"relation":"later_version","id":"11593","status":"public"}]},"publist_id":"7734","conference":{"location":"Budapest, Hungary","end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry","start_date":"2018-06-11"},"doi":"10.4230/LIPIcs.SoCG.2018.40"},{"language":[{"iso":"eng"}],"year":"2018","article_processing_charge":"No","title":"Recognizing weak embeddings of graphs","main_file_link":[{"url":"https://arxiv.org/abs/1709.09209","open_access":"1"}],"acknowledgement":"∗Research supported in part by the NSF awards CCF-1422311 and CCF-1423615, and the Science Without Borders program. The second author gratefully acknowledges support from Austrian Science Fund (FWF): M2281-N35.","oa_version":"Preprint","conference":{"end_date":"2018-01-10","start_date":"2018-01-07","name":"SODA: Symposium on Discrete Algorithms","location":"New Orleans, LA, USA"},"doi":"10.1137/1.9781611975031.20","publist_id":"7556","related_material":{"record":[{"relation":"later_version","id":"6982","status":"public"}]},"scopus_import":"1","month":"01","date_published":"2018-01-01T00:00:00Z","type":"conference","citation":{"mla":"Akitaya, Hugo, et al. <i>Recognizing Weak Embeddings of Graphs</i>. ACM, 2018, pp. 274–92, doi:<a href=\"https://doi.org/10.1137/1.9781611975031.20\">10.1137/1.9781611975031.20</a>.","ieee":"H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA, 2018, pp. 274–292.","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. In: ACM; 2018:274-292. doi:<a href=\"https://doi.org/10.1137/1.9781611975031.20\">10.1137/1.9781611975031.20</a>","chicago":"Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs,” 274–92. ACM, 2018. <a href=\"https://doi.org/10.1137/1.9781611975031.20\">https://doi.org/10.1137/1.9781611975031.20</a>.","ista":"Akitaya H, Fulek R, Tóth C. 2018. Recognizing weak embeddings of graphs. SODA: Symposium on Discrete Algorithms, 274–292.","short":"H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 2018, pp. 274–292.","apa":"Akitaya, H., Fulek, R., &#38; Tóth, C. (2018). Recognizing weak embeddings of graphs (pp. 274–292). Presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA: ACM. <a href=\"https://doi.org/10.1137/1.9781611975031.20\">https://doi.org/10.1137/1.9781611975031.20</a>"},"date_updated":"2023-09-15T12:19:32Z","date_created":"2018-12-11T11:45:45Z","status":"public","publisher":"ACM","page":"274 - 292","oa":1,"arxiv":1,"quality_controlled":"1","department":[{"_id":"UlWa"}],"day":"01","isi":1,"project":[{"call_identifier":"FWF","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"external_id":{"isi":["000483921200021"],"arxiv":["1709.09209"]},"author":[{"first_name":"Hugo","last_name":"Akitaya","full_name":"Akitaya, Hugo"},{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"first_name":"Csaba","last_name":"Tóth","full_name":"Tóth, Csaba"}],"publication_status":"published","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"309","abstract":[{"lang":"eng","text":"We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ' : G ! M of a graph G into a 2manifold M maps the vertices in V (G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map ' : G ! M comes from an embedding. A map ' : G ! M is a weak embedding if it can be perturbed into an embedding ψ: G ! M with k' \"k < \" for every &quot; &gt; 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl [14], which reduces to solving a system of linear equations over Z2. It runs in O(n2!) O(n4:75) time, where 2:373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually &quot;untangles&quot; the image '(G) into an embedding (G), or reports that ' is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations."}]},{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"file_id":"6518","relation":"main_file","creator":"kschuh","date_updated":"2020-07-14T12:47:33Z","content_type":"application/pdf","file_size":588982,"date_created":"2019-06-04T12:20:35Z","checksum":"fc7a643e29621c8bbe49d36b39081f31","access_level":"open_access","file_name":"2017_LIPIcs-Fulek.pdf"}],"date_created":"2019-06-04T12:11:52Z","status":"public","department":[{"_id":"UlWa"}],"day":"01","oa":1,"quality_controlled":"1","author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"}],"volume":92,"project":[{"grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"M02281"}],"_id":"6517","abstract":[{"text":"A (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing, whether a drawing of a planar graph G in the plane is approximable by an embedding, can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation system (or equivalently the faces) of the embedding of G and the choice of outer face are fixed. In other words, we show that c-planarity with embedded pipes is tractable for graphs with fixed embeddings. To the best of our knowledge an analogous result was previously known essentially only when G is a cycle.","lang":"eng"}],"publication_status":"published","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","year":"2017","language":[{"iso":"eng"}],"title":"Embedding graphs into embedded graphs","intvolume":"        92","ec_funded":1,"doi":"10.4230/LIPICS.ISAAC.2017.34","conference":{"location":"Phuket, Thailand","end_date":"2017-12-22","start_date":"2017-12-09","name":"ISAAC: International Symposium on Algorithms and Computation"},"file_date_updated":"2020-07-14T12:47:33Z","oa_version":"Published Version","article_number":"34","type":"conference","has_accepted_license":"1","date_updated":"2021-01-12T08:07:51Z","citation":{"ista":"Fulek R. 2017. Embedding graphs into embedded graphs. ISAAC: International Symposium on Algorithms and Computation vol. 92, 34.","chicago":"Fulek, Radoslav. “Embedding Graphs into Embedded Graphs,” Vol. 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">https://doi.org/10.4230/LIPICS.ISAAC.2017.34</a>.","apa":"Fulek, R. (2017). Embedding graphs into embedded graphs (Vol. 92). Presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">https://doi.org/10.4230/LIPICS.ISAAC.2017.34</a>","short":"R. Fulek, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"R. Fulek, “Embedding graphs into embedded graphs,” presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand, 2017, vol. 92.","mla":"Fulek, Radoslav. <i>Embedding Graphs into Embedded Graphs</i>. Vol. 92, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">10.4230/LIPICS.ISAAC.2017.34</a>.","ama":"Fulek R. Embedding graphs into embedded graphs. In: Vol 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">10.4230/LIPICS.ISAAC.2017.34</a>"},"scopus_import":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["510"],"date_published":"2017-12-01T00:00:00Z","month":"12"}]