[{"article_processing_charge":"No","day":"27","scopus_import":"1","date_published":"2023-07-27T00:00:00Z","citation":{"mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry, Springer Nature, 2023, doi:10.1007/s00454-023-00532-x.","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational Geometry (2023).","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.","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","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2023. The crossing Tverberg theorem. Discrete and Computational Geometry.","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","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” Discrete and Computational Geometry. Springer Nature, 2023."},"publication":"Discrete and Computational Geometry","article_type":"original","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."}],"type":"journal_article","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"13974","title":"The crossing Tverberg theorem","status":"public","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"07","doi":"10.1007/s00454-023-00532-x","language":[{"iso":"eng"}],"external_id":{"isi":["001038546500001"],"arxiv":["1812.04911"]},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1812.04911","open_access":"1"}],"oa":1,"project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF"}],"isi":1,"quality_controlled":"1","related_material":{"record":[{"id":"6647","status":"public","relation":"earlier_version"}]},"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek","full_name":"Fulek, Radoslav"},{"full_name":"Gärtner, Bernd","last_name":"Gärtner","first_name":"Bernd"},{"full_name":"Kupavskii, Andrey","last_name":"Kupavskii","first_name":"Andrey"},{"full_name":"Valtr, Pavel","last_name":"Valtr","first_name":"Pavel"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"date_updated":"2023-12-13T12:03:35Z","date_created":"2023-08-06T22:01:12Z","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).","year":"2023","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","publication_status":"epub_ahead"},{"year":"2022","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.","publication_status":"published","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"author":[{"full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek"},{"full_name":"Kynčl, Jan","first_name":"Jan","last_name":"Kynčl"}],"related_material":{"record":[{"id":"186","status":"public","relation":"earlier_version"}]},"date_updated":"2023-08-14T12:43:52Z","date_created":"2022-07-17T22:01:56Z","volume":68,"month":"09","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"external_id":{"isi":["000825014500001"],"arxiv":["1803.05085"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.05085"}],"isi":1,"quality_controlled":"1","project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"doi":"10.1007/s00454-022-00412-w","language":[{"iso":"eng"}],"type":"journal_article","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 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.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11593","status":"public","title":"The Z2-Genus of Kuratowski minors","intvolume":" 68","oa_version":"Preprint","scopus_import":"1","day":"01","article_processing_charge":"No","publication":"Discrete and Computational Geometry","citation":{"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.","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","ista":"Fulek R, Kynčl J. 2022. The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. 68, 425–447.","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","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.","short":"R. Fulek, J. Kynčl, Discrete and Computational Geometry 68 (2022) 425–447.","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."},"article_type":"original","page":"425-447","date_published":"2022-09-01T00:00:00Z"},{"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"month":"06","doi":"10.4230/LIPICS.SOCG.2019.39","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2019-06-21","location":"Portland, OR, United States","start_date":"2019-06-18"},"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"arxiv":["1903.08637"]},"project":[{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"quality_controlled":"1","file_date_updated":"2020-07-14T12:47:57Z","license":"https://creativecommons.org/licenses/by/4.0/","article_number":"39","author":[{"full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek"},{"last_name":"Kyncl","first_name":"Jan","full_name":"Kyncl, Jan"}],"volume":129,"date_updated":"2021-01-12T08:13:24Z","date_created":"2020-01-29T16:17:05Z","year":"2019","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","has_accepted_license":"1","article_processing_charge":"No","day":"01","scopus_import":1,"date_published":"2019-06-01T00:00:00Z","citation":{"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.","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.","short":"R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","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.","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.","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"},"publication":"35th International Symposium on Computational Geometry (SoCG 2019)","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"}],"type":"conference","alternative_title":["LIPIcs"],"file":[{"creator":"dernst","content_type":"application/pdf","file_size":628347,"file_name":"2019_LIPIcs_Fulek.pdf","access_level":"open_access","date_created":"2020-02-04T09:14:31Z","date_updated":"2020-07-14T12:47:57Z","checksum":"aac37b09118cc0ab58cf77129e691f8c","file_id":"7445","relation":"main_file"}],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7401","intvolume":" 129","status":"public","ddc":["000"],"title":"Z_2-Genus of graphs and minimum rank of partial symmetric matrices"},{"oa_version":"Preprint","_id":"5790","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","title":"Extending partial representations of circle graphs","status":"public","intvolume":" 91","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."}],"issue":"4","type":"journal_article","date_published":"2019-08-01T00:00:00Z","publication":"Journal of Graph Theory","citation":{"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.","short":"S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.","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.","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","ista":"Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of circle graphs. Journal of Graph Theory. 91(4), 365–394.","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","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."},"article_type":"original","page":"365-394","day":"01","article_processing_charge":"No","scopus_import":"1","author":[{"first_name":"Steven","last_name":"Chaplick","full_name":"Chaplick, Steven"},{"orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"full_name":"Klavík, Pavel","first_name":"Pavel","last_name":"Klavík"}],"date_updated":"2023-08-24T14:30:43Z","date_created":"2018-12-30T22:59:15Z","volume":91,"year":"2019","publication_status":"published","publisher":"Wiley","department":[{"_id":"UlWa"}],"ec_funded":1,"doi":"10.1002/jgt.22436","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1309.2399","open_access":"1"}],"oa":1,"external_id":{"arxiv":["1309.2399"],"isi":["000485392800004"]},"quality_controlled":"1","isi":1,"project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"month":"08","publication_identifier":{"issn":["03649024"]}},{"year":"2019","department":[{"_id":"UlWa"}],"publisher":"Elsevier","publication_status":"published","related_material":{"record":[{"id":"433","status":"public","relation":"earlier_version"}]},"author":[{"full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek"},{"first_name":"János","last_name":"Pach","full_name":"Pach, János"}],"volume":259,"date_created":"2019-01-20T22:59:17Z","date_updated":"2023-08-24T14:39:33Z","oa":1,"external_id":{"isi":["000466061100020"],"arxiv":["1708.08037"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.08037"}],"project":[{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"quality_controlled":"1","isi":1,"doi":"10.1016/j.dam.2018.12.025","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0166218X"]},"month":"04","_id":"5857","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","intvolume":" 259","status":"public","title":"Thrackles: An improved upper bound","oa_version":"Preprint","type":"journal_article","issue":"4","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 [Formula presented](n−1), and that this bound is best possible for infinitely many values of n."}],"citation":{"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.","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.","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","ista":"Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied Mathematics. 259(4), 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.","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"},"publication":"Discrete Applied Mathematics","page":"266-231","article_type":"original","date_published":"2019-04-30T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"30"},{"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1709.00508","open_access":"1"}],"external_id":{"isi":["000493267200003"],"arxiv":["1709.00508"]},"quality_controlled":"1","isi":1,"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"},{"grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs"}],"doi":"10.1007/s00493-019-3905-7","language":[{"iso":"eng"}],"month":"10","publication_identifier":{"issn":["0209-9683"],"eissn":["1439-6912"]},"year":"2019","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek","full_name":"Fulek, Radoslav"},{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"}],"date_updated":"2023-08-30T07:26:25Z","date_created":"2019-11-18T14:29:50Z","volume":39,"ec_funded":1,"publication":"Combinatorica","citation":{"ista":"Fulek R, Kynčl J. 2019. Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4. Combinatorica. 39(6), 1267–1279.","ieee":"R. Fulek and J. Kynčl, “Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4,” 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","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.","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."},"article_type":"original","page":"1267-1279","date_published":"2019-10-29T00:00:00Z","scopus_import":"1","day":"29","article_processing_charge":"No","_id":"7034","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","title":"Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4","status":"public","intvolume":" 39","oa_version":"Preprint","type":"journal_article","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"}],"issue":"6"},{"article_number":"50","publisher":"ACM","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2019","volume":15,"date_updated":"2023-09-15T12:19:31Z","date_created":"2019-11-04T15:45:17Z","related_material":{"record":[{"id":"309","relation":"earlier_version","status":"public"}]},"author":[{"full_name":"Akitaya, Hugo","last_name":"Akitaya","first_name":"Hugo"},{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"first_name":"Csaba","last_name":"Tóth","full_name":"Tóth, Csaba"}],"month":"10","project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs"}],"quality_controlled":"1","oa":1,"external_id":{"arxiv":["1709.09209"]},"main_file_link":[{"url":"https://arxiv.org/abs/1709.09209","open_access":"1"}],"language":[{"iso":"eng"}],"doi":"10.1145/3344549","type":"journal_article","issue":"4","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"}],"intvolume":" 15","status":"public","title":"Recognizing weak embeddings of graphs","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6982","oa_version":"Preprint","scopus_import":1,"day":"01","article_type":"original","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.","ista":"Akitaya H, Fulek R, Tóth C. 2019. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms. 15(4), 50.","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.","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."},"publication":"ACM Transactions on Algorithms","date_published":"2019-10-01T00:00:00Z"},{"project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs"}],"quality_controlled":"1","external_id":{"arxiv":["1812.04911"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"doi":"10.4230/LIPICS.SOCG.2019.38","conference":{"end_date":"2019-06-21","start_date":"2019-06-18","location":"Portland, OR, United States","name":"SoCG 2019: Symposium on Computational Geometry"},"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771047"]},"month":"06","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","year":"2019","volume":129,"date_created":"2019-07-17T10:35:04Z","date_updated":"2023-12-13T12:03:35Z","related_material":{"record":[{"id":"13974","status":"public","relation":"later_version"}]},"author":[{"first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav"},{"full_name":"Gärtner, Bernd","last_name":"Gärtner","first_name":"Bernd"},{"full_name":"Kupavskii, Andrey","first_name":"Andrey","last_name":"Kupavskii"},{"first_name":"Pavel","last_name":"Valtr","full_name":"Valtr, Pavel"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"file_date_updated":"2020-07-14T12:47:35Z","page":"38:1-38:13","citation":{"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","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.","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: 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","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.","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.","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."},"publication":"35th International Symposium on Computational Geometry","date_published":"2019-06-01T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"01","intvolume":" 129","ddc":["000","510"],"status":"public","title":"The crossing Tverberg theorem","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6647","oa_version":"Published Version","file":[{"checksum":"d6d017f8b41291b94d102294fa96ae9c","date_updated":"2020-07-14T12:47:35Z","date_created":"2019-07-24T06:54:52Z","file_id":"6667","relation":"main_file","creator":"dernst","content_type":"application/pdf","file_size":559837,"access_level":"open_access","file_name":"2019_LIPICS_Fulek.pdf"}],"alternative_title":["LIPIcs"],"type":"conference","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."}]},{"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."}],"type":"conference","alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"file":[{"access_level":"open_access","file_name":"2018_LIPIcs_Fulek.pdf","content_type":"application/pdf","file_size":718857,"creator":"dernst","relation":"main_file","file_id":"5701","checksum":"f1b94f1a75b37c414a1f61d59fb2cd4c","date_updated":"2020-07-14T12:45:19Z","date_created":"2018-12-17T12:33:52Z"}],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"185","intvolume":" 99","status":"public","title":"Hanani-Tutte for approximating maps of graphs","ddc":["510"],"has_accepted_license":"1","day":"01","scopus_import":1,"date_published":"2018-01-01T00:00:00Z","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: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.","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","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.","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.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","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."},"publist_id":"7735","file_date_updated":"2020-07-14T12:45:19Z","article_number":"39","author":[{"orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"full_name":"Kynčl, Jan","first_name":"Jan","last_name":"Kynčl"}],"volume":99,"date_created":"2018-12-11T11:45:04Z","date_updated":"2021-01-12T06:53:36Z","year":"2018","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","publication_identifier":{"isbn":["978-3-95977-066-8"]},"month":"01","doi":"10.4230/LIPIcs.SoCG.2018.39","conference":{"start_date":"2018-06-11","location":"Budapest, Hungary","end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry"},"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"project":[{"grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF"}],"quality_controlled":"1"},{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2018","volume":99,"date_created":"2018-12-11T11:45:05Z","date_updated":"2023-08-14T12:43:51Z","related_material":{"record":[{"id":"11593","status":"public","relation":"later_version"}]},"author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"}],"publist_id":"7734","project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","external_id":{"arxiv":["1803.05085"]},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1803.05085","open_access":"1"}],"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2018.40","conference":{"name":"SoCG: Symposium on Computational Geometry","location":"Budapest, Hungary","start_date":"2018-06-11","end_date":"2018-06-14"},"month":"06","intvolume":" 99","title":"The ℤ2-Genus of Kuratowski minors","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"186","oa_version":"Submitted Version","alternative_title":["LIPIcs"],"type":"conference","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."}],"page":"40.1 - 40.14","citation":{"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.","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.","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","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.","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.","short":"R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14."},"date_published":"2018-06-11T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"11"},{"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.08037"}],"external_id":{"arxiv":["1708.08037"]},"oa":1,"quality_controlled":"1","doi":"10.1007/978-3-319-73915-1_14","conference":{"end_date":"2017-09-27","start_date":"201-09-25","location":"Boston, MA, United States","name":"GD 2017: Graph Drawing and Network Visualization"},"language":[{"iso":"eng"}],"month":"01","year":"2018","publisher":"Springer","department":[{"_id":"UlWa"}],"publication_status":"published","related_material":{"record":[{"relation":"later_version","status":"public","id":"5857"}]},"author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav"},{"full_name":"Pach, János","last_name":"Pach","first_name":"János"}],"volume":10692,"date_created":"2018-12-11T11:46:27Z","date_updated":"2023-08-24T14:39:32Z","publist_id":"7390","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.","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.","short":"R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166.","ista":"Fulek R, Pach J. 2018. Thrackles: An improved upper bound. GD 2017: Graph Drawing and Network Visualization, LNCS, vol. 10692, 160–166.","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","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.","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"},"page":"160 - 166","date_published":"2018-01-21T00:00:00Z","scopus_import":1,"day":"21","_id":"433","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 10692","title":"Thrackles: An improved upper bound","status":"public","oa_version":"Submitted Version","type":"conference","alternative_title":["LNCS"],"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."}]},{"date_published":"2018-12-18T00:00:00Z","page":"229-241","citation":{"short":"R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.","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.","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.","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","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.","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","ista":"Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. Graph Drawing and Network Visualization, LNCS, vol. 11282, 229–241."},"article_processing_charge":"No","day":"18","scopus_import":"1","oa_version":"Preprint","status":"public","title":"Crossing minimization in perturbed drawings","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"5791","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."}],"alternative_title":["LNCS"],"type":"conference","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-04414-5_16","conference":{"name":"Graph Drawing and Network Visualization","start_date":"2018-09-26","location":"Barcelona, Spain","end_date":"2018-09-28"},"quality_controlled":"1","isi":1,"external_id":{"isi":["000672802500016"],"arxiv":["1808.07608"]},"main_file_link":[{"url":"https://arxiv.org/abs/1808.07608","open_access":"1"}],"oa":1,"publication_identifier":{"isbn":["9783030044138"]},"month":"12","volume":"11282 ","date_created":"2018-12-30T22:59:15Z","date_updated":"2023-09-11T12:49:55Z","author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Tóth","first_name":"Csaba D.","full_name":"Tóth, Csaba D."}],"department":[{"_id":"UlWa"}],"publisher":"Springer","publication_status":"published","year":"2018"},{"citation":{"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.","mla":"Akitaya, Hugo, et al. Recognizing Weak Embeddings of Graphs. ACM, 2018, pp. 274–92, doi:10.1137/1.9781611975031.20.","short":"H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 2018, pp. 274–292.","ista":"Akitaya H, Fulek R, Tóth C. 2018. Recognizing weak embeddings of graphs. SODA: Symposium on Discrete Algorithms, 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.","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","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. In: ACM; 2018:274-292. doi:10.1137/1.9781611975031.20"},"page":"274 - 292","date_published":"2018-01-01T00:00:00Z","scopus_import":"1","day":"01","article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"309","status":"public","title":"Recognizing weak embeddings of graphs","oa_version":"Preprint","type":"conference","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."}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.09209"}],"oa":1,"external_id":{"isi":["000483921200021"],"arxiv":["1709.09209"]},"quality_controlled":"1","isi":1,"project":[{"_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF"}],"conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2018-01-10","location":"New Orleans, LA, USA","start_date":"2018-01-07"},"doi":"10.1137/1.9781611975031.20","language":[{"iso":"eng"}],"month":"01","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.","year":"2018","publication_status":"published","publisher":"ACM","department":[{"_id":"UlWa"}],"author":[{"full_name":"Akitaya, Hugo","last_name":"Akitaya","first_name":"Hugo"},{"last_name":"Fulek","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"full_name":"Tóth, Csaba","last_name":"Tóth","first_name":"Csaba"}],"related_material":{"record":[{"id":"6982","status":"public","relation":"later_version"}]},"date_created":"2018-12-11T11:45:45Z","date_updated":"2023-09-15T12:19:32Z","publist_id":"7556"},{"type":"journal_article","issue":"1","abstract":[{"lang":"eng","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."}],"intvolume":" 21","status":"public","title":"Hanani-Tutte for radial planarity","ddc":["510"],"_id":"1113","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","file":[{"file_id":"6967","relation":"main_file","date_updated":"2019-10-24T10:54:37Z","date_created":"2019-10-24T10:54:37Z","success":1,"file_name":"2017_JournalGraphAlgorithms_Fulek.pdf","access_level":"open_access","creator":"dernst","content_type":"application/pdf","file_size":573623}],"scopus_import":1,"has_accepted_license":"1","article_processing_charge":"No","day":"01","page":"135 - 154","article_type":"original","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","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.","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","ista":"Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 21(1), 135–154.","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.","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."},"publication":"Journal of Graph Algorithms and Applications","date_published":"2017-01-01T00:00:00Z","ec_funded":1,"publist_id":"6254","file_date_updated":"2019-10-24T10:54:37Z","publisher":"Brown University","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2017","volume":21,"date_created":"2018-12-11T11:50:13Z","date_updated":"2023-02-23T10:05:57Z","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"1164"},{"id":"1595","status":"public","relation":"earlier_version"}]},"author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"first_name":"Michael","last_name":"Pelsmajer","full_name":"Pelsmajer, Michael"},{"full_name":"Schaefer, Marcus","first_name":"Marcus","last_name":"Schaefer"}],"month":"01","project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"quality_controlled":"1","oa":1,"external_id":{"arxiv":["1608.08662"]},"language":[{"iso":"eng"}],"doi":"10.7155/jgaa.00408"},{"conference":{"name":"ISAAC: International Symposium on Algorithms and Computation","location":"Phuket, Thailand","start_date":"2017-12-09","end_date":"2017-12-22"},"doi":"10.4230/LIPICS.ISAAC.2017.34","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"month":"12","author":[{"first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav"}],"date_created":"2019-06-04T12:11:52Z","date_updated":"2021-01-12T08:07:51Z","volume":92,"year":"2017","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2020-07-14T12:47:33Z","ec_funded":1,"article_number":"34","date_published":"2017-12-01T00:00:00Z","citation":{"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.","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.","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.","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","ista":"Fulek R. 2017. Embedding graphs into embedded graphs. ISAAC: International Symposium on Algorithms and Computation vol. 92, 34."},"day":"01","has_accepted_license":"1","scopus_import":1,"oa_version":"Published Version","file":[{"date_updated":"2020-07-14T12:47:33Z","date_created":"2019-06-04T12:20:35Z","checksum":"fc7a643e29621c8bbe49d36b39081f31","relation":"main_file","file_id":"6518","content_type":"application/pdf","file_size":588982,"creator":"kschuh","file_name":"2017_LIPIcs-Fulek.pdf","access_level":"open_access"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"6517","ddc":["510"],"status":"public","title":"Embedding graphs into embedded graphs","intvolume":" 92","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"}],"type":"conference"},{"month":"07","publication_identifier":{"issn":["10778926"]},"oa":1,"quality_controlled":"1","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"doi":"10.37236/6663","language":[{"iso":"eng"}],"article_number":"P3.18","file_date_updated":"2020-07-14T12:48:06Z","publist_id":"6859","ec_funded":1,"year":"2017","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"International Press","author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kynčl, Jan","last_name":"Kynčl","first_name":"Jan"},{"full_name":"Pálvölgyi, Dömötör","first_name":"Dömötör","last_name":"Pálvölgyi"}],"date_created":"2018-12-11T11:48:32Z","date_updated":"2022-03-18T12:58:53Z","volume":24,"scopus_import":"1","day":"28","article_processing_charge":"No","has_accepted_license":"1","publication":"Electronic Journal of Combinatorics","citation":{"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.","short":"R. Fulek, J. Kynčl, D. Pálvölgyi, Electronic Journal of Combinatorics 24 (2017).","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.","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.","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","ista":"Fulek R, Kynčl J, Pálvölgyi D. 2017. Unified Hanani Tutte theorem. Electronic Journal of Combinatorics. 24(3), P3.18.","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"},"article_type":"original","date_published":"2017-07-28T00:00:00Z","type":"journal_article","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."}],"issue":"3","_id":"795","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Unified Hanani Tutte theorem","ddc":["000"],"intvolume":" 24","oa_version":"Published Version","file":[{"relation":"main_file","file_id":"5853","checksum":"ef320cff0f062051e858f929be6a3581","date_created":"2019-01-18T14:04:08Z","date_updated":"2020-07-14T12:48:06Z","access_level":"open_access","file_name":"2017_ElectrCombi_Fulek.pdf","content_type":"application/pdf","file_size":236944,"creator":"dernst"}]},{"date_created":"2018-12-11T11:48:32Z","date_updated":"2023-09-27T12:15:16Z","volume":66,"author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"first_name":"Hossein","last_name":"Mojarrad","full_name":"Mojarrad, Hossein"},{"first_name":"Márton","last_name":"Naszódi","full_name":"Naszódi, Márton"},{"full_name":"Solymosi, József","last_name":"Solymosi","first_name":"József"},{"full_name":"Stich, Sebastian","last_name":"Stich","first_name":"Sebastian"},{"full_name":"Szedlák, May","first_name":"May","last_name":"Szedlák"}],"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Elsevier","year":"2017","publist_id":"6861","ec_funded":1,"language":[{"iso":"eng"}],"doi":"10.1016/j.comgeo.2017.07.002","isi":1,"quality_controlled":"1","project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"oa":1,"external_id":{"isi":["000412039700003"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1701.08183"}],"month":"01","publication_identifier":{"issn":["09257721"]},"oa_version":"Submitted Version","status":"public","title":"On the existence of ordinary triangles","intvolume":" 66","_id":"793","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","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"}],"type":"journal_article","date_published":"2017-01-01T00:00:00Z","page":"28 - 31","publication":"Computational Geometry: Theory and Applications","citation":{"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.","short":"R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, M. Szedlák, Computational Geometry: Theory and Applications 66 (2017) 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.","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","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.","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.","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"},"day":"01","article_processing_charge":"No"},{"abstract":[{"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.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","title":"C-planarity of embedded cyclic c-graphs","status":"public","intvolume":" 66","_id":"794","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","day":"01","article_processing_charge":"No","scopus_import":"1","date_published":"2017-12-01T00:00:00Z","page":"1 - 13","publication":"Computational Geometry: Theory and Applications","citation":{"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","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","ieee":"R. Fulek, “C-planarity of embedded cyclic c-graphs,” Computational Geometry: Theory and Applications, vol. 66. Elsevier, pp. 1–13, 2017.","ista":"Fulek R. 2017. C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications. 66, 1–13.","short":"R. Fulek, Computational Geometry: Theory and Applications 66 (2017) 1–13.","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.","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."},"publist_id":"6860","date_created":"2018-12-11T11:48:32Z","date_updated":"2023-09-27T12:14:49Z","volume":66,"author":[{"full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek"}],"related_material":{"record":[{"id":"1165","status":"public","relation":"earlier_version"}]},"publication_status":"published","publisher":"Elsevier","department":[{"_id":"UlWa"}],"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.","year":"2017","month":"12","language":[{"iso":"eng"}],"doi":"10.1016/j.comgeo.2017.06.016","isi":1,"quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1602.01346","open_access":"1"}],"oa":1,"external_id":{"isi":["000412039700001"]}},{"doi":"10.1007/978-3-319-44543-4_3","conference":{"name":"IWOCA: International Workshop on Combinatorial Algorithms","start_date":"2016-08-17","location":"Helsinki, Finland","end_date":"2018-08-19"},"language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1610.07144","open_access":"1"}],"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"quality_controlled":"1","month":"08","author":[{"first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav"}],"volume":9843,"date_created":"2018-12-11T11:51:31Z","date_updated":"2021-01-12T06:50:03Z","year":"2016","publisher":"Springer","department":[{"_id":"UlWa"}],"publication_status":"published","ec_funded":1,"publist_id":"5901","date_published":"2016-08-09T00:00:00Z","citation":{"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.","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.","short":"R. Fulek, in:, Springer, 2016, pp. 31–42.","ista":"Fulek R. 2016. Bounded embeddings of graphs in the plane. IWOCA: International Workshop on Combinatorial Algorithms, LNCS, vol. 9843, 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.","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"},"page":"31 - 42","day":"09","scopus_import":1,"oa_version":"Preprint","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1348","intvolume":" 9843","title":"Bounded embeddings of graphs in the plane","status":"public","abstract":[{"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.","lang":"eng"}],"type":"conference","alternative_title":["LNCS"]},{"date_published":"2016-12-08T00:00:00Z","page":"468 - 481","citation":{"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","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.","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.","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","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.","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."},"day":"08","article_processing_charge":"No","scopus_import":1,"oa_version":"Preprint","status":"public","title":"Hanani-Tutte for radial planarity II","intvolume":" 9801","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1164","abstract":[{"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.","lang":"eng"}],"alternative_title":["LNCS"],"type":"conference","language":[{"iso":"eng"}],"conference":{"name":"GD: Graph Drawing and Network Visualization","location":"Athens, Greece","start_date":"2016-09-19","end_date":"2016-09-21"},"doi":"10.1007/978-3-319-50106-2_36","quality_controlled":"1","project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1608.08662"}],"oa":1,"external_id":{"arxiv":["1608.08662"]},"month":"12","date_created":"2018-12-11T11:50:29Z","date_updated":"2023-02-23T10:05:57Z","volume":9801,"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek","full_name":"Fulek, Radoslav"},{"full_name":"Pelsmajer, Michael","first_name":"Michael","last_name":"Pelsmajer"},{"full_name":"Schaefer, Marcus","last_name":"Schaefer","first_name":"Marcus"}],"related_material":{"record":[{"id":"1113","status":"public","relation":"later_version"},{"relation":"earlier_version","status":"public","id":"1595"}]},"publication_status":"published","publisher":"Springer","department":[{"_id":"UlWa"}],"year":"2016","ec_funded":1,"publist_id":"6193"},{"_id":"1165","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","title":"C-planarity of embedded cyclic c-graphs","status":"public","oa_version":"Preprint","type":"conference","alternative_title":["LNCS"],"abstract":[{"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.","lang":"eng"}],"citation":{"ama":"Fulek R. C-planarity of embedded cyclic c-graphs. In: Vol 9801. Springer; 2016:94-106. doi:10.1007/978-3-319-50106-2_8","apa":"Fulek, R. (2016). C-planarity of embedded cyclic c-graphs (Vol. 9801, pp. 94–106). Presented at the GD: Graph Drawing and Network Visualization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-319-50106-2_8","ieee":"R. Fulek, “C-planarity of embedded cyclic c-graphs,” presented at the GD: Graph Drawing and Network Visualization, Athens, Greece, 2016, vol. 9801, pp. 94–106.","ista":"Fulek R. 2016. C-planarity of embedded cyclic c-graphs. GD: Graph Drawing and Network Visualization, LNCS, vol. 9801, 94–106.","short":"R. Fulek, in:, Springer, 2016, pp. 94–106.","mla":"Fulek, Radoslav. C-Planarity of Embedded Cyclic c-Graphs. Vol. 9801, Springer, 2016, pp. 94–106, doi:10.1007/978-3-319-50106-2_8.","chicago":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs,” 9801:94–106. Springer, 2016. https://doi.org/10.1007/978-3-319-50106-2_8."},"page":"94 - 106","date_published":"2016-12-08T00:00:00Z","scopus_import":1,"day":"08","year":"2016","acknowledgement":"R. Fulek—The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].\r\nI would like to thank Jan Kynčl and Dömötör Pálvölgyi for many comments and suggestions that helped to improve the presentation of the result.","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer","author":[{"full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"794"}]},"date_created":"2018-12-11T11:50:30Z","date_updated":"2023-09-27T12:14:48Z","volume":"9801 ","publist_id":"6192","ec_funded":1,"main_file_link":[{"url":"https://arxiv.org/abs/1602.01346","open_access":"1"}],"oa":1,"quality_controlled":"1","project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734"}],"conference":{"start_date":"2016-09-19","location":"Athens, Greece","end_date":"2016-09-21","name":"GD: Graph Drawing and Network Visualization"},"doi":"10.1007/978-3-319-50106-2_8","language":[{"iso":"eng"}],"month":"12"},{"department":[{"_id":"UlWa"}],"publisher":"Springer","publication_status":"published","acknowledgement":"The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].","year":"2015","volume":9411,"date_updated":"2023-02-21T16:23:36Z","date_created":"2018-12-11T11:52:55Z","related_material":{"record":[{"id":"1113","status":"public","relation":"later_version"},{"id":"1164","status":"public","relation":"later_version"}]},"author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav"},{"full_name":"Pelsmajer, Michael","last_name":"Pelsmajer","first_name":"Michael"},{"last_name":"Schaefer","first_name":"Marcus","full_name":"Schaefer, Marcus"}],"ec_funded":1,"publist_id":"5576","file_date_updated":"2020-07-14T12:45:03Z","project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-27261-0_9","conference":{"end_date":"2015-09-26","location":"Los Angeles, CA, USA","start_date":"2015-09-24","name":"GD: Graph Drawing and Network Visualization"},"month":"11","intvolume":" 9411","title":"Hanani-Tutte for radial planarity","status":"public","ddc":["510"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1595","file":[{"creator":"system","file_size":330135,"content_type":"application/pdf","access_level":"open_access","file_name":"IST-2016-594-v1+1_HTCylinder_GD_Revision.pdf","checksum":"685f91bd077a951ba067d42cce75409e","date_updated":"2020-07-14T12:45:03Z","date_created":"2018-12-12T10:08:36Z","file_id":"4697","relation":"main_file"}],"oa_version":"Submitted Version","pubrep_id":"594","alternative_title":["LNCS"],"type":"conference","abstract":[{"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. 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 Tóth.","lang":"eng"}],"page":"99 - 110","citation":{"chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity,” 9411:99–110. Springer, 2015. https://doi.org/10.1007/978-3-319-27261-0_9.","short":"R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2015, pp. 99–110.","mla":"Fulek, Radoslav, et al. Hanani-Tutte for Radial Planarity. Vol. 9411, Springer, 2015, pp. 99–110, doi:10.1007/978-3-319-27261-0_9.","apa":"Fulek, R., Pelsmajer, M., & Schaefer, M. (2015). Hanani-Tutte for radial planarity (Vol. 9411, pp. 99–110). Presented at the GD: Graph Drawing and Network Visualization, Los Angeles, CA, USA: Springer. https://doi.org/10.1007/978-3-319-27261-0_9","ieee":"R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,” presented at the GD: Graph Drawing and Network Visualization, Los Angeles, CA, USA, 2015, vol. 9411, pp. 99–110.","ista":"Fulek R, Pelsmajer M, Schaefer M. 2015. Hanani-Tutte for radial planarity. GD: Graph Drawing and Network Visualization, LNCS, vol. 9411, 99–110.","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. In: Vol 9411. Springer; 2015:99-110. doi:10.1007/978-3-319-27261-0_9"},"date_published":"2015-11-27T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"27"},{"conference":{"end_date":"2015-09-26","start_date":"2015-09-24","location":"Los Angeles, CA, United States","name":"GD: Graph Drawing and Network Visualization"},"doi":"10.1007/978-3-319-27261-0_31","language":[{"iso":"eng"}],"oa":1,"quality_controlled":"1","project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"month":"11","publication_identifier":{"isbn":["978-3-319-27260-3"]},"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek","full_name":"Fulek, Radoslav"},{"full_name":"Radoičić, Radoš","last_name":"Radoičić","first_name":"Radoš"}],"date_created":"2018-12-11T11:52:56Z","date_updated":"2022-01-28T09:20:50Z","volume":9411,"year":"2015","publication_status":"published","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:45:04Z","ec_funded":1,"publist_id":"5575","date_published":"2015-11-27T00:00:00Z","publication":"Graph Drawing and Network Visualization","citation":{"chicago":"Fulek, Radoslav, and Radoš Radoičić. “Vertical Visibility among Parallel Polygons in Three Dimensions.” In Graph Drawing and Network Visualization, 9411:373–79. Springer Nature, 2015. https://doi.org/10.1007/978-3-319-27261-0_31.","mla":"Fulek, Radoslav, and Radoš Radoičić. “Vertical Visibility among Parallel Polygons in Three Dimensions.” Graph Drawing and Network Visualization, vol. 9411, Springer Nature, 2015, pp. 373–79, doi:10.1007/978-3-319-27261-0_31.","short":"R. Fulek, R. Radoičić, in:, Graph Drawing and Network Visualization, Springer Nature, 2015, pp. 373–379.","ista":"Fulek R, Radoičić R. 2015.Vertical visibility among parallel polygons in three dimensions. In: Graph Drawing and Network Visualization. LNCS, vol. 9411, 373–379.","apa":"Fulek, R., & Radoičić, R. (2015). Vertical visibility among parallel polygons in three dimensions. In Graph Drawing and Network Visualization (Vol. 9411, pp. 373–379). Los Angeles, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-319-27261-0_31","ieee":"R. Fulek and R. Radoičić, “Vertical visibility among parallel polygons in three dimensions,” in Graph Drawing and Network Visualization, vol. 9411, Springer Nature, 2015, pp. 373–379.","ama":"Fulek R, Radoičić R. Vertical visibility among parallel polygons in three dimensions. In: Graph Drawing and Network Visualization. Vol 9411. Springer Nature; 2015:373-379. doi:10.1007/978-3-319-27261-0_31"},"page":"373 - 379","day":"27","article_processing_charge":"No","has_accepted_license":"1","scopus_import":"1","pubrep_id":"595","file":[{"file_id":"5258","relation":"main_file","checksum":"eec04f86c5921d04f025d5791db9b965","date_created":"2018-12-12T10:17:06Z","date_updated":"2020-07-14T12:45:04Z","access_level":"open_access","file_name":"IST-2016-595-v1+1_VerticalVisibilityGDRevision.pdf","creator":"system","file_size":312992,"content_type":"application/pdf"}],"oa_version":"Submitted Version","_id":"1596","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","ddc":["510"],"status":"public","title":"Vertical visibility among parallel polygons in three dimensions","intvolume":" 9411","abstract":[{"lang":"eng","text":"Let C={C1,...,Cn} denote a collection of translates of a regular convex k-gon in the plane with the stacking order. The collection C forms a visibility clique if for everyi < j the intersection Ci and (Ci ∩ Cj)\\⋃i<l<jCl =∅.elements that are stacked between them, i.e., We show that if C forms a visibility clique its size is bounded from above by O(k4) thereby improving the upper bound of 22k from the aforementioned paper. We also obtain an upper bound of 22(k/2)+2 on the size of a visibility clique for homothetes of a convex (not necessarily regular) k-gon."}],"type":"book_chapter","alternative_title":["LNCS"]},{"oa":1,"external_id":{"arxiv":["1305.4519"]},"project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","doi":"10.37236/5002","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1077-8926"]},"month":"11","year":"2015","acknowledgement":"e research leading to these results has received funding fromthe People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme(FP7/2007-2013) under REA grant agreement no [291734], and ESF Eurogiga project GraDR as GAˇCRGIG/11/E023.","publisher":"Electronic Journal of Combinatorics","department":[{"_id":"UlWa"}],"publication_status":"published","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"10793"}]},"author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"full_name":"Kynčl, Jan","last_name":"Kynčl","first_name":"Jan"},{"first_name":"Igor","last_name":"Malinovič","full_name":"Malinovič, Igor"},{"full_name":"Pálvölgyi, Dömötör","last_name":"Pálvölgyi","first_name":"Dömötör"}],"volume":22,"date_created":"2018-12-11T11:53:12Z","date_updated":"2023-02-21T16:03:02Z","article_number":"P4.24 ","publist_id":"5511","ec_funded":1,"file_date_updated":"2020-07-14T12:45:08Z","citation":{"ama":"Fulek R, Kynčl J, Malinovič I, Pálvölgyi D. Clustered planarity testing revisited. Electronic Journal of Combinatorics. 2015;22(4). doi:10.37236/5002","ista":"Fulek R, Kynčl J, Malinovič I, Pálvölgyi D. 2015. Clustered planarity testing revisited. Electronic Journal of Combinatorics. 22(4), P4.24.","ieee":"R. Fulek, J. Kynčl, I. Malinovič, and D. Pálvölgyi, “Clustered planarity testing revisited,” Electronic Journal of Combinatorics, vol. 22, no. 4. Electronic Journal of Combinatorics, 2015.","apa":"Fulek, R., Kynčl, J., Malinovič, I., & Pálvölgyi, D. (2015). Clustered planarity testing revisited. Electronic Journal of Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/5002","mla":"Fulek, Radoslav, et al. “Clustered Planarity Testing Revisited.” Electronic Journal of Combinatorics, vol. 22, no. 4, P4.24, Electronic Journal of Combinatorics, 2015, doi:10.37236/5002.","short":"R. Fulek, J. Kynčl, I. Malinovič, D. Pálvölgyi, Electronic Journal of Combinatorics 22 (2015).","chicago":"Fulek, Radoslav, Jan Kynčl, Igor Malinovič, and Dömötör Pálvölgyi. “Clustered Planarity Testing Revisited.” Electronic Journal of Combinatorics. Electronic Journal of Combinatorics, 2015. https://doi.org/10.37236/5002."},"publication":"Electronic Journal of Combinatorics","article_type":"original","date_published":"2015-11-13T00:00:00Z","scopus_import":"1","article_processing_charge":"No","has_accepted_license":"1","day":"13","_id":"1642","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 22","title":"Clustered planarity testing revisited","status":"public","ddc":["514","516"],"pubrep_id":"714","oa_version":"Published Version","file":[{"creator":"system","content_type":"application/pdf","file_size":443655,"access_level":"open_access","file_name":"IST-2016-714-v1+1_5002-15499-3-PB.pdf","checksum":"40b5920b49ee736694f59f39588ee206","date_updated":"2020-07-14T12:45:08Z","date_created":"2018-12-12T10:15:03Z","file_id":"5120","relation":"main_file"}],"type":"journal_article","issue":"4","abstract":[{"lang":"eng","text":"The Hanani-Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident to at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm."}]},{"place":"Cham","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","year":"2014","date_updated":"2023-02-23T10:08:04Z","date_created":"2022-02-25T10:32:14Z","volume":8871,"author":[{"last_name":"Fulek","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"},{"full_name":"Malinović, Igor","first_name":"Igor","last_name":"Malinović"},{"last_name":"Pálvölgyi","first_name":"Dömötör","full_name":"Pálvölgyi, Dömötör"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"1642"}]},"month":"01","publication_identifier":{"issn":["0302-9743"]},"quality_controlled":"1","external_id":{"arxiv":["1305.4519"]},"language":[{"iso":"eng"}],"doi":"10.1007/978-3-662-45803-7_36","alternative_title":["LNCS"],"type":"conference","abstract":[{"lang":"eng","text":"The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this classical result to clustered graphs with two disjoint clusters, and show that a straightforward extension of our result to flat clustered graphs with three or more disjoint clusters is not possible.\r\n\r\nWe also give a new and short proof for a related result by Di Battista and Frati based on the matroid intersection algorithm."}],"status":"public","title":"Clustered planarity testing revisited","intvolume":" 8871","_id":"10793","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","scopus_import":"1","day":"01","article_processing_charge":"No","page":"428-436","publication":"International Symposium on Graph Drawing","citation":{"chicago":"Fulek, Radoslav, Jan Kynčl, Igor Malinović, and Dömötör Pálvölgyi. “Clustered Planarity Testing Revisited.” In International Symposium on Graph Drawing, 8871:428–36. Cham: Springer Nature, 2014. https://doi.org/10.1007/978-3-662-45803-7_36.","mla":"Fulek, Radoslav, et al. “Clustered Planarity Testing Revisited.” International Symposium on Graph Drawing, vol. 8871, Springer Nature, 2014, pp. 428–36, doi:10.1007/978-3-662-45803-7_36.","short":"R. Fulek, J. Kynčl, I. Malinović, D. Pálvölgyi, in:, International Symposium on Graph Drawing, Springer Nature, Cham, 2014, pp. 428–436.","ista":"Fulek R, Kynčl J, Malinović I, Pálvölgyi D. 2014. Clustered planarity testing revisited. International Symposium on Graph Drawing. , LNCS, vol. 8871, 428–436.","apa":"Fulek, R., Kynčl, J., Malinović, I., & Pálvölgyi, D. (2014). Clustered planarity testing revisited. In International Symposium on Graph Drawing (Vol. 8871, pp. 428–436). Cham: Springer Nature. https://doi.org/10.1007/978-3-662-45803-7_36","ieee":"R. Fulek, J. Kynčl, I. Malinović, and D. Pálvölgyi, “Clustered planarity testing revisited,” in International Symposium on Graph Drawing, 2014, vol. 8871, pp. 428–436.","ama":"Fulek R, Kynčl J, Malinović I, Pálvölgyi D. Clustered planarity testing revisited. In: International Symposium on Graph Drawing. Vol 8871. Cham: Springer Nature; 2014:428-436. doi:10.1007/978-3-662-45803-7_36"},"date_published":"2014-01-01T00:00:00Z"}]