[{"department":[{"_id":"UlWa"}],"date_updated":"2023-12-13T12:03:35Z","type":"journal_article","article_type":"original","status":"public","_id":"13974","related_material":{"record":[{"relation":"earlier_version","id":"6647","status":"public"}]},"publication_status":"epub_ahead","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"language":[{"iso":"eng"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1812.04911","open_access":"1"}],"scopus_import":"1","month":"07","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 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.","lang":"eng"}],"oa_version":"Preprint","article_processing_charge":"No","external_id":{"arxiv":["1812.04911"],"isi":["001038546500001"]},"author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Bernd","last_name":"Gärtner","full_name":"Gärtner, Bernd"},{"first_name":"Andrey","full_name":"Kupavskii, Andrey","last_name":"Kupavskii"},{"first_name":"Pavel","last_name":"Valtr","full_name":"Valtr, Pavel"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"title":"The crossing Tverberg theorem","citation":{"ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. Discrete and Computational Geometry. 2023. doi:10.1007/s00454-023-00532-x","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2023). The crossing Tverberg theorem. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00532-x","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational Geometry (2023).","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” Discrete and Computational Geometry. Springer Nature, 2023.","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry, Springer Nature, 2023, doi:10.1007/s00454-023-00532-x.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2023. The crossing Tverberg theorem. Discrete and Computational Geometry.","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00532-x."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"date_created":"2023-08-06T22:01:12Z","doi":"10.1007/s00454-023-00532-x","date_published":"2023-07-27T00:00:00Z","year":"2023","isi":1,"publication":"Discrete and Computational Geometry","day":"27","oa":1,"publisher":"Springer Nature","quality_controlled":"1","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)."},{"project":[{"call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs"}],"citation":{"mla":"Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” Discrete and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 425–47, doi:10.1007/s00454-022-00412-w.","short":"R. Fulek, J. Kynčl, Discrete and Computational Geometry 68 (2022) 425–447.","ieee":"R. Fulek and J. Kynčl, “The Z2-Genus of Kuratowski minors,” Discrete and Computational Geometry, vol. 68. Springer Nature, pp. 425–447, 2022.","ama":"Fulek R, Kynčl J. The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. 2022;68:425-447. doi:10.1007/s00454-022-00412-w","apa":"Fulek, R., & Kynčl, J. (2022). The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00412-w","chicago":"Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” Discrete and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-022-00412-w.","ista":"Fulek R, Kynčl J. 2022. The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. 68, 425–447."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Fulek","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jan","full_name":"Kynčl, Jan","last_name":"Kynčl"}],"external_id":{"arxiv":["1803.05085"],"isi":["000825014500001"]},"article_processing_charge":"No","title":"The Z2-Genus of Kuratowski minors","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.","quality_controlled":"1","publisher":"Springer Nature","oa":1,"isi":1,"year":"2022","day":"01","publication":"Discrete and Computational Geometry","page":"425-447","doi":"10.1007/s00454-022-00412-w","date_published":"2022-09-01T00:00:00Z","date_created":"2022-07-17T22:01:56Z","_id":"11593","type":"journal_article","article_type":"original","status":"public","date_updated":"2023-08-14T12:43:52Z","department":[{"_id":"UlWa"}],"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."}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.05085"}],"month":"09","intvolume":" 68","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publication_status":"published","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"186"}]},"volume":68},{"ddc":["000"],"date_updated":"2021-01-12T08:13:24Z","file_date_updated":"2020-07-14T12:47:57Z","department":[{"_id":"UlWa"}],"_id":"7401","status":"public","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2019-06-18","location":"Portland, OR, United States","end_date":"2019-06-21"},"file":[{"file_id":"7445","checksum":"aac37b09118cc0ab58cf77129e691f8c","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2019_LIPIcs_Fulek.pdf","date_created":"2020-02-04T09:14:31Z","file_size":628347,"date_updated":"2020-07-14T12:47:57Z","creator":"dernst"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"publication_status":"published","volume":129,"oa_version":"Published Version","abstract":[{"lang":"eng","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. "}],"month":"06","intvolume":" 129","scopus_import":1,"alternative_title":["LIPIcs"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","chicago":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” In 35th International Symposium on Computational Geometry (SoCG 2019), Vol. 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.39.","ieee":"R. Fulek and J. Kyncl, “Z_2-Genus of graphs and minimum rank of partial symmetric matrices,” in 35th International Symposium on Computational Geometry (SoCG 2019), Portland, OR, United States, 2019, vol. 129.","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., & Kyncl, J. (2019). Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In 35th International Symposium on Computational Geometry (SoCG 2019) (Vol. 129). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.39","ama":"Fulek R, Kyncl J. Z_2-Genus of graphs and minimum rank of partial symmetric matrices. In: 35th International Symposium on Computational Geometry (SoCG 2019). Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.SOCG.2019.39","mla":"Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices.” 35th International Symposium on Computational Geometry (SoCG 2019), vol. 129, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.SOCG.2019.39."},"title":"Z_2-Genus of graphs and minimum rank of partial symmetric matrices","author":[{"first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774"},{"last_name":"Kyncl","full_name":"Kyncl, Jan","first_name":"Jan"}],"article_processing_charge":"No","external_id":{"arxiv":["1903.08637"]},"article_number":"39","project":[{"call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281"}],"day":"01","publication":"35th International Symposium on Computational Geometry (SoCG 2019)","has_accepted_license":"1","year":"2019","date_published":"2019-06-01T00:00:00Z","doi":"10.4230/LIPICS.SOCG.2019.39","date_created":"2020-01-29T16:17:05Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1},{"status":"public","article_type":"original","type":"journal_article","_id":"5790","department":[{"_id":"UlWa"}],"date_updated":"2023-08-24T14:30:43Z","intvolume":" 91","month":"08","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1309.2399"}],"scopus_import":"1","oa_version":"Preprint","abstract":[{"lang":"eng","text":"The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some predrawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire graph G, that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of G. Our main result is an O(n3) time algorithm for partial representation extension of circle graphs, where n is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest."}],"ec_funded":1,"volume":91,"issue":"4","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["03649024"]},"project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}],"title":"Extending partial representations of circle graphs","article_processing_charge":"No","external_id":{"isi":["000485392800004"],"arxiv":["1309.2399"]},"author":[{"first_name":"Steven","full_name":"Chaplick, Steven","last_name":"Chaplick"},{"first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek"},{"first_name":"Pavel","last_name":"Klavík","full_name":"Klavík, Pavel"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” Journal of Graph Theory. Wiley, 2019. https://doi.org/10.1002/jgt.22436.","ista":"Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of circle graphs. Journal of Graph Theory. 91(4), 365–394.","mla":"Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.” Journal of Graph Theory, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:10.1002/jgt.22436.","apa":"Chaplick, S., Fulek, R., & Klavík, P. (2019). Extending partial representations of circle graphs. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.22436","ama":"Chaplick S, Fulek R, Klavík P. Extending partial representations of circle graphs. Journal of Graph Theory. 2019;91(4):365-394. doi:10.1002/jgt.22436","ieee":"S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” Journal of Graph Theory, vol. 91, no. 4. Wiley, pp. 365–394, 2019.","short":"S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394."},"oa":1,"quality_controlled":"1","publisher":"Wiley","date_created":"2018-12-30T22:59:15Z","date_published":"2019-08-01T00:00:00Z","doi":"10.1002/jgt.22436","page":"365-394","publication":"Journal of Graph Theory","day":"01","year":"2019","isi":1},{"date_published":"2019-04-30T00:00:00Z","doi":"10.1016/j.dam.2018.12.025","date_created":"2019-01-20T22:59:17Z","page":"266-231","day":"30","publication":"Discrete Applied Mathematics","isi":1,"year":"2019","publisher":"Elsevier","quality_controlled":"1","oa":1,"title":"Thrackles: An improved upper bound","author":[{"orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav"},{"full_name":"Pach, János","last_name":"Pach","first_name":"János"}],"external_id":{"isi":["000466061100020"],"arxiv":["1708.08037"]},"article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete Applied Mathematics. Elsevier, 2019. https://doi.org/10.1016/j.dam.2018.12.025.","ista":"Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied Mathematics. 259(4), 266–231.","mla":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete Applied Mathematics, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:10.1016/j.dam.2018.12.025.","short":"R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” Discrete Applied Mathematics, vol. 259, no. 4. Elsevier, pp. 266–231, 2019.","ama":"Fulek R, Pach J. Thrackles: An improved upper bound. Discrete Applied Mathematics. 2019;259(4):266-231. doi:10.1016/j.dam.2018.12.025","apa":"Fulek, R., & Pach, J. (2019). Thrackles: An improved upper bound. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2018.12.025"},"project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281"}],"related_material":{"record":[{"id":"433","status":"public","relation":"earlier_version"}]},"volume":259,"issue":"4","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0166218X"]},"publication_status":"published","month":"04","intvolume":" 259","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.08037"}],"oa_version":"Preprint","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"}],"department":[{"_id":"UlWa"}],"date_updated":"2023-08-24T14:39:33Z","status":"public","type":"journal_article","article_type":"original","_id":"5857"},{"oa_version":"Preprint","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"}],"intvolume":" 39","month":"10","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.00508"}],"scopus_import":"1","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"eissn":["1439-6912"],"issn":["0209-9683"]},"ec_funded":1,"issue":"6","volume":39,"_id":"7034","status":"public","article_type":"original","type":"journal_article","date_updated":"2023-08-30T07:26:25Z","department":[{"_id":"UlWa"}],"oa":1,"quality_controlled":"1","publisher":"Springer Nature","publication":"Combinatorica","day":"29","year":"2019","isi":1,"date_created":"2019-11-18T14:29:50Z","doi":"10.1007/s00493-019-3905-7","date_published":"2019-10-29T00:00:00Z","page":"1267-1279","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"},{"call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte Theorem on the Surface of Genus 4.” Combinatorica. Springer Nature, 2019. https://doi.org/10.1007/s00493-019-3905-7.","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.","mla":"Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte Theorem on the Surface of Genus 4.” Combinatorica, vol. 39, no. 6, Springer Nature, 2019, pp. 1267–79, doi:10.1007/s00493-019-3905-7.","short":"R. Fulek, J. Kynčl, Combinatorica 39 (2019) 1267–1279.","ieee":"R. Fulek and J. Kynčl, “Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4,” Combinatorica, vol. 39, no. 6. Springer Nature, pp. 1267–1279, 2019.","apa":"Fulek, R., & Kynčl, J. (2019). Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-019-3905-7","ama":"Fulek R, Kynčl J. Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. Combinatorica. 2019;39(6):1267-1279. doi:10.1007/s00493-019-3905-7"},"title":"Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4","external_id":{"isi":["000493267200003"],"arxiv":["1709.00508"]},"article_processing_charge":"No","author":[{"first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek"},{"last_name":"Kynčl","full_name":"Kynčl, Jan","first_name":"Jan"}]},{"oa":1,"quality_controlled":"1","publisher":"ACM","date_created":"2019-11-04T15:45:17Z","date_published":"2019-10-01T00:00:00Z","doi":"10.1145/3344549","year":"2019","publication":"ACM Transactions on Algorithms","day":"01","project":[{"grant_number":"M02281","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"article_number":"50","external_id":{"arxiv":["1709.09209"]},"author":[{"last_name":"Akitaya","full_name":"Akitaya, Hugo","first_name":"Hugo"},{"first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek"},{"full_name":"Tóth, Csaba","last_name":"Tóth","first_name":"Csaba"}],"title":"Recognizing weak embeddings of graphs","citation":{"ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 2019;15(4). doi:10.1145/3344549","apa":"Akitaya, H., Fulek, R., & Tóth, C. (2019). Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. ACM. https://doi.org/10.1145/3344549","ieee":"H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” ACM Transactions on Algorithms, vol. 15, no. 4. ACM, 2019.","short":"H. Akitaya, R. Fulek, C. Tóth, ACM Transactions on Algorithms 15 (2019).","mla":"Akitaya, Hugo, et al. “Recognizing Weak Embeddings of Graphs.” ACM Transactions on Algorithms, vol. 15, no. 4, 50, ACM, 2019, doi:10.1145/3344549.","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.” ACM Transactions on Algorithms. ACM, 2019. https://doi.org/10.1145/3344549."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://arxiv.org/abs/1709.09209","open_access":"1"}],"scopus_import":1,"intvolume":" 15","month":"10","abstract":[{"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","lang":"eng"}],"oa_version":"Preprint","issue":"4","volume":15,"related_material":{"record":[{"status":"public","id":"309","relation":"earlier_version"}]},"publication_status":"published","language":[{"iso":"eng"}],"type":"journal_article","article_type":"original","status":"public","_id":"6982","department":[{"_id":"UlWa"}],"date_updated":"2023-09-15T12:19:31Z"},{"file":[{"checksum":"d6d017f8b41291b94d102294fa96ae9c","file_id":"6667","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2019_LIPICS_Fulek.pdf","date_created":"2019-07-24T06:54:52Z","creator":"dernst","file_size":559837,"date_updated":"2020-07-14T12:47:35Z"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783959771047"],"issn":["1868-8969"]},"publication_status":"published","related_material":{"record":[{"id":"13974","status":"public","relation":"later_version"}]},"volume":129,"oa_version":"Published Version","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 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."}],"month":"06","intvolume":" 129","scopus_import":1,"alternative_title":["LIPIcs"],"ddc":["000","510"],"date_updated":"2023-12-13T12:03:35Z","file_date_updated":"2020-07-14T12:47:35Z","department":[{"_id":"UlWa"}],"_id":"6647","status":"public","type":"conference","conference":{"location":"Portland, OR, United States","end_date":"2019-06-21","start_date":"2019-06-18","name":"SoCG 2019: Symposium on Computational Geometry"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"day":"01","publication":"35th International Symposium on Computational Geometry","has_accepted_license":"1","year":"2019","doi":"10.4230/LIPICS.SOCG.2019.38","date_published":"2019-06-01T00:00:00Z","date_created":"2019-07-17T10:35:04Z","page":"38:1-38:13","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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.","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in 35th International Symposium on Computational Geometry, Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019). The crossing Tverberg theorem. In 35th International Symposium on Computational Geometry (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38.","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.","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” In 35th International Symposium on Computational Geometry, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38."},"title":"The crossing Tverberg theorem","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek"},{"last_name":"Gärtner","full_name":"Gärtner, Bernd","first_name":"Bernd"},{"last_name":"Kupavskii","full_name":"Kupavskii, Andrey","first_name":"Andrey"},{"first_name":"Pavel","full_name":"Valtr, Pavel","last_name":"Valtr"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner"}],"external_id":{"arxiv":["1812.04911"]},"project":[{"call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs"}]},{"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","date_created":"2018-12-11T11:45:04Z","doi":"10.4230/LIPIcs.SoCG.2018.39","date_published":"2018-01-01T00:00:00Z","day":"01","year":"2018","has_accepted_license":"1","project":[{"grant_number":"M02281","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"article_number":"39","title":"Hanani-Tutte for approximating maps of graphs","author":[{"first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek"},{"first_name":"Jan","last_name":"Kynčl","full_name":"Kynčl, Jan"}],"publist_id":"7735","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","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.","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:10.4230/LIPIcs.SoCG.2018.39","apa":"Fulek, R., & 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. https://doi.org/10.4230/LIPIcs.SoCG.2018.39","mla":"Fulek, Radoslav, and Jan Kynčl. Hanani-Tutte for Approximating Maps of Graphs. Vol. 99, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.39.","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.","chicago":"Fulek, Radoslav, and Jan Kynčl. “Hanani-Tutte for Approximating Maps of Graphs,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.39."},"intvolume":" 99","month":"01","scopus_import":1,"alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"oa_version":"Published Version","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 "pipes" 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."}],"volume":99,"language":[{"iso":"eng"}],"file":[{"file_id":"5701","checksum":"f1b94f1a75b37c414a1f61d59fb2cd4c","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2018_LIPIcs_Fulek.pdf","date_created":"2018-12-17T12:33:52Z","file_size":718857,"date_updated":"2020-07-14T12:45:19Z","creator":"dernst"}],"publication_status":"published","publication_identifier":{"isbn":["978-3-95977-066-8"]},"status":"public","conference":{"start_date":"2018-06-11","end_date":"2018-06-14","location":"Budapest, Hungary","name":"SoCG: Symposium on Computational Geometry"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"conference","_id":"185","file_date_updated":"2020-07-14T12:45:19Z","department":[{"_id":"UlWa"}],"ddc":["510"],"date_updated":"2021-01-12T06:53:36Z"},{"_id":"186","status":"public","conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2018-06-11","end_date":"2018-06-14","location":"Budapest, Hungary"},"type":"conference","date_updated":"2023-08-14T12:43:51Z","department":[{"_id":"UlWa"}],"oa_version":"Submitted Version","abstract":[{"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.","lang":"eng"}],"intvolume":" 99","month":"06","main_file_link":[{"url":"https://arxiv.org/abs/1803.05085","open_access":"1"}],"scopus_import":"1","alternative_title":["LIPIcs"],"language":[{"iso":"eng"}],"publication_status":"published","related_material":{"record":[{"status":"public","id":"11593","relation":"later_version"}]},"volume":99,"project":[{"name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Fulek, Radoslav, and Jan Kynčl. The ℤ2-Genus of Kuratowski Minors. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14, doi:10.4230/LIPIcs.SoCG.2018.40.","apa":"Fulek, R., & 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. https://doi.org/10.4230/LIPIcs.SoCG.2018.40","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:10.4230/LIPIcs.SoCG.2018.40","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.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14.","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. https://doi.org/10.4230/LIPIcs.SoCG.2018.40.","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."},"title":"The ℤ2-Genus of Kuratowski minors","external_id":{"arxiv":["1803.05085"]},"article_processing_charge":"No","publist_id":"7734","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek"},{"last_name":"Kynčl","full_name":"Kynčl, Jan","first_name":"Jan"}],"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","day":"11","year":"2018","date_created":"2018-12-11T11:45:05Z","doi":"10.4230/LIPIcs.SoCG.2018.40","date_published":"2018-06-11T00:00:00Z","page":"40.1 - 40.14"},{"date_updated":"2023-08-24T14:39:32Z","department":[{"_id":"UlWa"}],"_id":"433","status":"public","type":"conference","conference":{"location":"Boston, MA, United States","end_date":"2017-09-27","start_date":"201-09-25","name":"GD 2017: Graph Drawing and Network Visualization"},"language":[{"iso":"eng"}],"publication_status":"published","volume":10692,"related_material":{"record":[{"relation":"later_version","status":"public","id":"5857"}]},"oa_version":"Submitted Version","abstract":[{"lang":"eng","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 3/2(n-1), and that this bound is best possible for infinitely many values of n."}],"month":"01","intvolume":" 10692","scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"url":"https://arxiv.org/abs/1708.08037","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound,” 10692:160–66. Springer, 2018. https://doi.org/10.1007/978-3-319-73915-1_14.","ista":"Fulek R, Pach J. 2018. Thrackles: An improved upper bound. GD 2017: Graph Drawing and Network Visualization, LNCS, vol. 10692, 160–166.","mla":"Fulek, Radoslav, and János Pach. Thrackles: An Improved Upper Bound. Vol. 10692, Springer, 2018, pp. 160–66, doi:10.1007/978-3-319-73915-1_14.","apa":"Fulek, R., & Pach, J. (2018). Thrackles: An improved upper bound (Vol. 10692, pp. 160–166). Presented at the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States: Springer. https://doi.org/10.1007/978-3-319-73915-1_14","ama":"Fulek R, Pach J. Thrackles: An improved upper bound. In: Vol 10692. Springer; 2018:160-166. doi:10.1007/978-3-319-73915-1_14","short":"R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166.","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” presented at the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States, 2018, vol. 10692, pp. 160–166."},"title":"Thrackles: An improved upper bound","author":[{"orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"János","full_name":"Pach, János","last_name":"Pach"}],"publist_id":"7390","external_id":{"arxiv":["1708.08037"]},"day":"21","year":"2018","doi":"10.1007/978-3-319-73915-1_14","date_published":"2018-01-21T00:00:00Z","date_created":"2018-12-11T11:46:27Z","page":"160 - 166","quality_controlled":"1","publisher":"Springer","oa":1},{"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"mla":"Fulek, Radoslav, and Csaba D. Tóth. Crossing Minimization in Perturbed Drawings. Vol. 11282, Springer, 2018, pp. 229–41, doi:10.1007/978-3-030-04414-5_16.","short":"R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.","ieee":"R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented at the Graph Drawing and Network Visualization, Barcelona, Spain, 2018, vol. 11282, pp. 229–241.","ama":"Fulek R, Tóth CD. Crossing minimization in perturbed drawings. In: Vol 11282. Springer; 2018:229-241. doi:10.1007/978-3-030-04414-5_16","apa":"Fulek, R., & Tóth, C. D. (2018). Crossing minimization in perturbed drawings (Vol. 11282, pp. 229–241). Presented at the Graph Drawing and Network Visualization, Barcelona, Spain: Springer. https://doi.org/10.1007/978-3-030-04414-5_16","chicago":"Fulek, Radoslav, and Csaba D. Tóth. “Crossing Minimization in Perturbed Drawings,” 11282:229–41. Springer, 2018. https://doi.org/10.1007/978-3-030-04414-5_16.","ista":"Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. Graph Drawing and Network Visualization, LNCS, vol. 11282, 229–241."},"title":"Crossing minimization in perturbed drawings","author":[{"orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Csaba D.","last_name":"Tóth","full_name":"Tóth, Csaba D."}],"article_processing_charge":"No","external_id":{"isi":["000672802500016"],"arxiv":["1808.07608"]},"publisher":"Springer","quality_controlled":"1","oa":1,"day":"18","isi":1,"year":"2018","date_published":"2018-12-18T00:00:00Z","doi":"10.1007/978-3-030-04414-5_16","date_created":"2018-12-30T22:59:15Z","page":"229-241","_id":"5791","status":"public","type":"conference","conference":{"name":"Graph Drawing and Network Visualization","start_date":"2018-09-26","location":"Barcelona, Spain","end_date":"2018-09-28"},"date_updated":"2023-09-11T12:49:55Z","department":[{"_id":"UlWa"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily small ε>0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An ε-perturbation, for every ε>0, is given by a piecewise linear map (Formula Presented), where with ||·|| is the uniform norm (i.e., sup norm). We present a polynomial-time solution for this optimization problem when G is a cycle and the map φ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii) when φ may have spurs and G is a cycle or a union of disjoint paths."}],"month":"12","scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1808.07608"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783030044138"]},"publication_status":"published","volume":"11282 "},{"scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1709.09209","open_access":"1"}],"month":"01","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 " > 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 "untangles" 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."}],"oa_version":"Preprint","related_material":{"record":[{"status":"public","id":"6982","relation":"later_version"}]},"publication_status":"published","language":[{"iso":"eng"}],"type":"conference","conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2018-01-10","location":"New Orleans, LA, USA","start_date":"2018-01-07"},"status":"public","_id":"309","department":[{"_id":"UlWa"}],"date_updated":"2023-09-15T12:19:32Z","publisher":"ACM","quality_controlled":"1","oa":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.","page":"274 - 292","date_published":"2018-01-01T00:00:00Z","doi":"10.1137/1.9781611975031.20","date_created":"2018-12-11T11:45:45Z","isi":1,"year":"2018","day":"01","project":[{"grant_number":"M02281","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"publist_id":"7556","author":[{"first_name":"Hugo","full_name":"Akitaya, Hugo","last_name":"Akitaya"},{"last_name":"Fulek","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav"},{"full_name":"Tóth, Csaba","last_name":"Tóth","first_name":"Csaba"}],"external_id":{"arxiv":["1709.09209"],"isi":["000483921200021"]},"article_processing_charge":"No","title":"Recognizing weak embeddings of graphs","citation":{"mla":"Akitaya, Hugo, et al. Recognizing Weak Embeddings of Graphs. ACM, 2018, pp. 274–92, doi:10.1137/1.9781611975031.20.","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. In: ACM; 2018:274-292. doi:10.1137/1.9781611975031.20","apa":"Akitaya, H., Fulek, R., & 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. https://doi.org/10.1137/1.9781611975031.20","short":"H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 2018, pp. 274–292.","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.","chicago":"Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs,” 274–92. ACM, 2018. https://doi.org/10.1137/1.9781611975031.20.","ista":"Akitaya H, Fulek R, Tóth C. 2018. Recognizing weak embeddings of graphs. SODA: Symposium on Discrete Algorithms, 274–292."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1"},{"title":"Hanani-Tutte for radial planarity","external_id":{"arxiv":["1608.08662"]},"article_processing_charge":"No","author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pelsmajer","full_name":"Pelsmajer, Michael","first_name":"Michael"},{"full_name":"Schaefer, Marcus","last_name":"Schaefer","first_name":"Marcus"}],"publist_id":"6254","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 2017;21(1):135-154. doi:10.7155/jgaa.00408","apa":"Fulek, R., Pelsmajer, M., & Schaefer, M. (2017). Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00408","ieee":"R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,” Journal of Graph Algorithms and Applications, vol. 21, no. 1. Brown University, pp. 135–154, 2017.","short":"R. Fulek, M. Pelsmajer, M. Schaefer, Journal of Graph Algorithms and Applications 21 (2017) 135–154.","mla":"Fulek, Radoslav, et al. “Hanani-Tutte for Radial Planarity.” Journal of Graph Algorithms and Applications, vol. 21, no. 1, Brown University, 2017, pp. 135–54, doi:10.7155/jgaa.00408.","ista":"Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 21(1), 135–154.","chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity.” Journal of Graph Algorithms and Applications. Brown University, 2017. https://doi.org/10.7155/jgaa.00408."},"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"date_created":"2018-12-11T11:50:13Z","doi":"10.7155/jgaa.00408","date_published":"2017-01-01T00:00:00Z","page":"135 - 154","publication":"Journal of Graph Algorithms and Applications","day":"01","year":"2017","has_accepted_license":"1","oa":1,"publisher":"Brown University","quality_controlled":"1","file_date_updated":"2019-10-24T10:54:37Z","department":[{"_id":"UlWa"}],"ddc":["510"],"date_updated":"2023-02-23T10:05:57Z","status":"public","article_type":"original","type":"journal_article","_id":"1113","ec_funded":1,"related_material":{"record":[{"relation":"earlier_version","id":"1164","status":"public"},{"status":"public","id":"1595","relation":"earlier_version"}]},"volume":21,"issue":"1","language":[{"iso":"eng"}],"file":[{"file_name":"2017_JournalGraphAlgorithms_Fulek.pdf","date_created":"2019-10-24T10:54:37Z","creator":"dernst","file_size":573623,"date_updated":"2019-10-24T10:54:37Z","success":1,"file_id":"6967","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"publication_status":"published","intvolume":" 21","month":"01","scopus_import":1,"oa_version":"Published Version","abstract":[{"text":"A drawing of a graph G is radial if the vertices of G are placed on concentric circles C 1 , . . . , C k with common center c , and edges are drawn radially : every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Toth.","lang":"eng"}]},{"article_number":"34","project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"},{"call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","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. https://doi.org/10.4230/LIPICS.ISAAC.2017.34.","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. https://doi.org/10.4230/LIPICS.ISAAC.2017.34","ama":"Fulek R. Embedding graphs into embedded graphs. In: Vol 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ISAAC.2017.34","ieee":"R. Fulek, “Embedding graphs into embedded graphs,” presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand, 2017, vol. 92.","short":"R. Fulek, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Fulek, Radoslav. Embedding Graphs into Embedded Graphs. Vol. 92, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ISAAC.2017.34."},"title":"Embedding graphs into embedded graphs","author":[{"first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek"}],"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","day":"01","year":"2017","has_accepted_license":"1","date_created":"2019-06-04T12:11:52Z","doi":"10.4230/LIPICS.ISAAC.2017.34","date_published":"2017-12-01T00:00:00Z","_id":"6517","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"ISAAC: International Symposium on Algorithms and Computation","start_date":"2017-12-09","end_date":"2017-12-22","location":"Phuket, Thailand"},"type":"conference","ddc":["510"],"date_updated":"2021-01-12T08:07:51Z","department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:47:33Z","oa_version":"Published Version","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"}],"intvolume":" 92","month":"12","scopus_import":1,"language":[{"iso":"eng"}],"file":[{"checksum":"fc7a643e29621c8bbe49d36b39081f31","file_id":"6518","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2019-06-04T12:20:35Z","file_name":"2017_LIPIcs-Fulek.pdf","creator":"kschuh","date_updated":"2020-07-14T12:47:33Z","file_size":588982}],"publication_status":"published","ec_funded":1,"volume":92},{"ec_funded":1,"issue":"3","volume":24,"language":[{"iso":"eng"}],"file":[{"creator":"dernst","file_size":236944,"date_updated":"2020-07-14T12:48:06Z","file_name":"2017_ElectrCombi_Fulek.pdf","date_created":"2019-01-18T14:04:08Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"ef320cff0f062051e858f929be6a3581","file_id":"5853"}],"publication_status":"published","publication_identifier":{"issn":["10778926"]},"intvolume":" 24","month":"07","scopus_import":"1","oa_version":"Published Version","abstract":[{"lang":"eng","text":"We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph G has a drawing D in the plane where every pair of independent edges crosses an even number of times, then G has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in D. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof."}],"department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:48:06Z","ddc":["000"],"date_updated":"2022-03-18T12:58:53Z","status":"public","article_type":"original","type":"journal_article","_id":"795","date_created":"2018-12-11T11:48:32Z","doi":"10.37236/6663","date_published":"2017-07-28T00:00:00Z","publication":"Electronic Journal of Combinatorics","day":"28","year":"2017","has_accepted_license":"1","oa":1,"publisher":"International Press","quality_controlled":"1","title":"Unified Hanani Tutte theorem","article_processing_charge":"No","publist_id":"6859","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek"},{"last_name":"Kynčl","full_name":"Kynčl, Jan","first_name":"Jan"},{"first_name":"Dömötör","last_name":"Pálvölgyi","full_name":"Pálvölgyi, Dömötör"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Fulek, Radoslav, et al. “Unified Hanani Tutte Theorem.” Electronic Journal of Combinatorics, vol. 24, no. 3, P3.18, International Press, 2017, doi:10.37236/6663.","apa":"Fulek, R., Kynčl, J., & Pálvölgyi, D. (2017). Unified Hanani Tutte theorem. Electronic Journal of Combinatorics. International Press. https://doi.org/10.37236/6663","ama":"Fulek R, Kynčl J, Pálvölgyi D. Unified Hanani Tutte theorem. Electronic Journal of Combinatorics. 2017;24(3). doi:10.37236/6663","ieee":"R. Fulek, J. Kynčl, and D. Pálvölgyi, “Unified Hanani Tutte theorem,” Electronic Journal of Combinatorics, vol. 24, no. 3. International Press, 2017.","short":"R. Fulek, J. Kynčl, D. Pálvölgyi, Electronic Journal of Combinatorics 24 (2017).","chicago":"Fulek, Radoslav, Jan Kynčl, and Dömötör Pálvölgyi. “Unified Hanani Tutte Theorem.” Electronic Journal of Combinatorics. International Press, 2017. https://doi.org/10.37236/6663.","ista":"Fulek R, Kynčl J, Pálvölgyi D. 2017. Unified Hanani Tutte theorem. Electronic Journal of Combinatorics. 24(3), P3.18."},"project":[{"grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"article_number":"P3.18"},{"day":"01","publication":"Computational Geometry: Theory and Applications","isi":1,"year":"2017","date_published":"2017-01-01T00:00:00Z","doi":"10.1016/j.comgeo.2017.07.002","date_created":"2018-12-11T11:48:32Z","page":"28 - 31","quality_controlled":"1","publisher":"Elsevier","oa":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. 2017. On the existence of ordinary triangles. Computational Geometry: Theory and Applications. 66, 28–31.","chicago":"Fulek, Radoslav, Hossein Mojarrad, Márton Naszódi, József Solymosi, Sebastian Stich, and May Szedlák. “On the Existence of Ordinary Triangles.” Computational Geometry: Theory and Applications. Elsevier, 2017. https://doi.org/10.1016/j.comgeo.2017.07.002.","ieee":"R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, and M. Szedlák, “On the existence of ordinary triangles,” Computational Geometry: Theory and Applications, vol. 66. Elsevier, pp. 28–31, 2017.","short":"R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, M. Szedlák, Computational Geometry: Theory and Applications 66 (2017) 28–31.","ama":"Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. On the existence of ordinary triangles. Computational Geometry: Theory and Applications. 2017;66:28-31. doi:10.1016/j.comgeo.2017.07.002","apa":"Fulek, R., Mojarrad, H., Naszódi, M., Solymosi, J., Stich, S., & Szedlák, M. (2017). On the existence of ordinary triangles. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2017.07.002","mla":"Fulek, Radoslav, et al. “On the Existence of Ordinary Triangles.” Computational Geometry: Theory and Applications, vol. 66, Elsevier, 2017, pp. 28–31, doi:10.1016/j.comgeo.2017.07.002."},"title":"On the existence of ordinary triangles","publist_id":"6861","author":[{"first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek"},{"first_name":"Hossein","last_name":"Mojarrad","full_name":"Mojarrad, Hossein"},{"full_name":"Naszódi, Márton","last_name":"Naszódi","first_name":"Márton"},{"first_name":"József","last_name":"Solymosi","full_name":"Solymosi, József"},{"full_name":"Stich, Sebastian","last_name":"Stich","first_name":"Sebastian"},{"last_name":"Szedlák","full_name":"Szedlák, May","first_name":"May"}],"article_processing_charge":"No","external_id":{"isi":["000412039700003"]},"project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["09257721"]},"publication_status":"published","volume":66,"ec_funded":1,"oa_version":"Submitted Version","abstract":[{"text":"Let P be a finite point set in the plane. A cordinary triangle in P is a subset of P consisting of three non-collinear points such that each of the three lines determined by the three points contains at most c points of P . Motivated by a question of Erdös, and answering a question of de Zeeuw, we prove that there exists a constant c > 0such that P contains a c-ordinary triangle, provided that P is not contained in the union of two lines. Furthermore, the number of c-ordinary triangles in P is Ω(| P |). ","lang":"eng"}],"month":"01","intvolume":" 66","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1701.08183"}],"date_updated":"2023-09-27T12:15:16Z","department":[{"_id":"UlWa"}],"_id":"793","status":"public","type":"journal_article"},{"acknowledgement":"I would like to thank Jan Kynčl, Dömötör Pálvölgyi and anonymous referees for many comments and suggestions that helped to improve the presentation of the result.","oa":1,"quality_controlled":"1","publisher":"Elsevier","year":"2017","isi":1,"publication":"Computational Geometry: Theory and Applications","day":"01","page":"1 - 13","date_created":"2018-12-11T11:48:32Z","date_published":"2017-12-01T00:00:00Z","doi":"10.1016/j.comgeo.2017.06.016","citation":{"apa":"Fulek, R. (2017). C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2017.06.016","ama":"Fulek R. C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications. 2017;66:1-13. doi:10.1016/j.comgeo.2017.06.016","short":"R. Fulek, Computational Geometry: Theory and Applications 66 (2017) 1–13.","ieee":"R. Fulek, “C-planarity of embedded cyclic c-graphs,” Computational Geometry: Theory and Applications, vol. 66. Elsevier, pp. 1–13, 2017.","mla":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” Computational Geometry: Theory and Applications, vol. 66, Elsevier, 2017, pp. 1–13, doi:10.1016/j.comgeo.2017.06.016.","ista":"Fulek R. 2017. C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications. 66, 1–13.","chicago":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” Computational Geometry: Theory and Applications. Elsevier, 2017. https://doi.org/10.1016/j.comgeo.2017.06.016."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","external_id":{"isi":["000412039700001"]},"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek"}],"publist_id":"6860","title":"C-planarity of embedded cyclic c-graphs","abstract":[{"lang":"eng","text":"We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle."}],"oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1602.01346","open_access":"1"}],"scopus_import":"1","intvolume":" 66","month":"12","publication_status":"published","language":[{"iso":"eng"}],"volume":66,"related_material":{"record":[{"relation":"earlier_version","id":"1165","status":"public"}]},"_id":"794","type":"journal_article","status":"public","date_updated":"2023-09-27T12:14:49Z","department":[{"_id":"UlWa"}]},{"volume":9843,"ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","month":"08","intvolume":" 9843","scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1610.07144"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"A drawing in the plane (ℝ2) of a graph G = (V,E) equipped with a function γ : V → ℕ is x-bounded if (i) x(u) < x(v) whenever γ(u) < γ(v) and (ii) γ(u) ≤ γ(w) ≤ γ(v), where uv ∈ E and γ(u) ≤ γ(v), whenever x(w) ∈ x(uv), where x(.) denotes the projection to the xaxis.We prove a characterization of isotopy classes of embeddings of connected graphs equipped with γ in the plane containing an x-bounded embedding.Then we present an efficient algorithm, which relies on our result, for testing the existence of an x-bounded embedding if the given graph is a forest.This partially answers a question raised recently by Angelini et al.and Chang et al., and proves that c-planarity testing of flat clustered graphs with three clusters is tractable when the underlying abstract graph is a forest."}],"department":[{"_id":"UlWa"}],"date_updated":"2021-01-12T06:50:03Z","status":"public","type":"conference","conference":{"name":"IWOCA: International Workshop on Combinatorial Algorithms","start_date":"2016-08-17","end_date":"2018-08-19","location":"Helsinki, Finland"},"_id":"1348","date_published":"2016-08-09T00:00:00Z","doi":"10.1007/978-3-319-44543-4_3","date_created":"2018-12-11T11:51:31Z","page":"31 - 42","day":"09","year":"2016","quality_controlled":"1","publisher":"Springer","oa":1,"title":"Bounded embeddings of graphs in the plane","author":[{"orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav"}],"publist_id":"5901","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Fulek, R. (2016). Bounded embeddings of graphs in the plane (Vol. 9843, pp. 31–42). Presented at the IWOCA: International Workshop on Combinatorial Algorithms, Helsinki, Finland: Springer. https://doi.org/10.1007/978-3-319-44543-4_3","ama":"Fulek R. Bounded embeddings of graphs in the plane. In: Vol 9843. Springer; 2016:31-42. doi:10.1007/978-3-319-44543-4_3","short":"R. Fulek, in:, Springer, 2016, pp. 31–42.","ieee":"R. Fulek, “Bounded embeddings of graphs in the plane,” presented at the IWOCA: International Workshop on Combinatorial Algorithms, Helsinki, Finland, 2016, vol. 9843, pp. 31–42.","mla":"Fulek, Radoslav. Bounded Embeddings of Graphs in the Plane. Vol. 9843, Springer, 2016, pp. 31–42, doi:10.1007/978-3-319-44543-4_3.","ista":"Fulek R. 2016. Bounded embeddings of graphs in the plane. IWOCA: International Workshop on Combinatorial Algorithms, LNCS, vol. 9843, 31–42.","chicago":"Fulek, Radoslav. “Bounded Embeddings of Graphs in the Plane,” 9843:31–42. Springer, 2016. https://doi.org/10.1007/978-3-319-44543-4_3."},"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}]},{"language":[{"iso":"eng"}],"publication_status":"published","related_material":{"record":[{"relation":"later_version","id":"1113","status":"public"},{"id":"1595","status":"public","relation":"earlier_version"}]},"volume":9801,"ec_funded":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, … , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. A pair of edges e and f in a graph is independent if e and f do not share a vertex. We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing."}],"month":"12","intvolume":" 9801","alternative_title":["LNCS"],"scopus_import":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1608.08662"}],"date_updated":"2023-02-23T10:05:57Z","department":[{"_id":"UlWa"}],"_id":"1164","status":"public","type":"conference","conference":{"end_date":"2016-09-21","location":"Athens, Greece","start_date":"2016-09-19","name":"GD: Graph Drawing and Network Visualization"},"day":"08","year":"2016","doi":"10.1007/978-3-319-50106-2_36","date_published":"2016-12-08T00:00:00Z","date_created":"2018-12-11T11:50:29Z","page":"468 - 481","quality_controlled":"1","publisher":"Springer","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Fulek R, Pelsmajer M, Schaefer M. 2016. Hanani-Tutte for radial planarity II. GD: Graph Drawing and Network Visualization, LNCS, vol. 9801, 468–481.","chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity II,” 9801:468–81. Springer, 2016. https://doi.org/10.1007/978-3-319-50106-2_36.","short":"R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2016, pp. 468–481.","ieee":"R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity II,” presented at the GD: Graph Drawing and Network Visualization, Athens, Greece, 2016, vol. 9801, pp. 468–481.","apa":"Fulek, R., Pelsmajer, M., & Schaefer, M. (2016). Hanani-Tutte for radial planarity II (Vol. 9801, pp. 468–481). Presented at the GD: Graph Drawing and Network Visualization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-319-50106-2_36","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity II. In: Vol 9801. Springer; 2016:468-481. doi:10.1007/978-3-319-50106-2_36","mla":"Fulek, Radoslav, et al. Hanani-Tutte for Radial Planarity II. Vol. 9801, Springer, 2016, pp. 468–81, doi:10.1007/978-3-319-50106-2_36."},"title":"Hanani-Tutte for radial planarity II","publist_id":"6193","author":[{"first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek"},{"last_name":"Pelsmajer","full_name":"Pelsmajer, Michael","first_name":"Michael"},{"first_name":"Marcus","last_name":"Schaefer","full_name":"Schaefer, Marcus"}],"article_processing_charge":"No","external_id":{"arxiv":["1608.08662"]},"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}]}]