[{"volume":21,"page":"135 - 154","oa_version":"Published Version","article_type":"original","file":[{"date_created":"2019-10-24T10:54:37Z","date_updated":"2019-10-24T10:54:37Z","access_level":"open_access","file_size":573623,"file_name":"2017_JournalGraphAlgorithms_Fulek.pdf","content_type":"application/pdf","relation":"main_file","creator":"dernst","file_id":"6967","success":1}],"quality_controlled":"1","oa":1,"citation":{"ieee":"R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,” <i>Journal of Graph Algorithms and Applications</i>, vol. 21, no. 1. Brown University, pp. 135–154, 2017.","chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2017. <a href=\"https://doi.org/10.7155/jgaa.00408\">https://doi.org/10.7155/jgaa.00408</a>.","short":"R. Fulek, M. Pelsmajer, M. Schaefer, Journal of Graph Algorithms and Applications 21 (2017) 135–154.","ista":"Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 21(1), 135–154.","mla":"Fulek, Radoslav, et al. “Hanani-Tutte for Radial Planarity.” <i>Journal of Graph Algorithms and Applications</i>, vol. 21, no. 1, Brown University, 2017, pp. 135–54, doi:<a href=\"https://doi.org/10.7155/jgaa.00408\">10.7155/jgaa.00408</a>.","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. <i>Journal of Graph Algorithms and Applications</i>. 2017;21(1):135-154. doi:<a href=\"https://doi.org/10.7155/jgaa.00408\">10.7155/jgaa.00408</a>","apa":"Fulek, R., Pelsmajer, M., &#38; Schaefer, M. (2017). Hanani-Tutte for radial planarity. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.00408\">https://doi.org/10.7155/jgaa.00408</a>"},"day":"01","file_date_updated":"2019-10-24T10:54:37Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","status":"public","department":[{"_id":"UlWa"}],"title":"Hanani-Tutte for radial planarity","publisher":"Brown University","project":[{"name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7"}],"external_id":{"arxiv":["1608.08662"]},"publist_id":"6254","article_processing_charge":"No","publication":"Journal of Graph Algorithms and Applications","date_published":"2017-01-01T00:00:00Z","scopus_import":1,"_id":"1113","date_created":"2018-12-11T11:50:13Z","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."}],"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav"},{"last_name":"Pelsmajer","first_name":"Michael","full_name":"Pelsmajer, Michael"},{"full_name":"Schaefer, Marcus","first_name":"Marcus","last_name":"Schaefer"}],"ec_funded":1,"related_material":{"record":[{"id":"1164","relation":"earlier_version","status":"public"},{"id":"1595","relation":"earlier_version","status":"public"}]},"publication_status":"published","intvolume":"        21","type":"journal_article","arxiv":1,"date_updated":"2023-02-23T10:05:57Z","ddc":["510"],"doi":"10.7155/jgaa.00408","year":"2017","language":[{"iso":"eng"}],"month":"01"},{"publication_identifier":{"issn":["09257721"]},"isi":1,"quality_controlled":"1","oa":1,"citation":{"short":"R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, M. Szedlák, Computational Geometry: Theory and Applications 66 (2017) 28–31.","ieee":"R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, and M. Szedlák, “On the existence of ordinary triangles,” <i>Computational Geometry: Theory and Applications</i>, vol. 66. Elsevier, pp. 28–31, 2017.","chicago":"Fulek, Radoslav, Hossein Mojarrad, Márton Naszódi, József Solymosi, Sebastian Stich, and May Szedlák. “On the Existence of Ordinary Triangles.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2017. <a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">https://doi.org/10.1016/j.comgeo.2017.07.002</a>.","ama":"Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. On the existence of ordinary triangles. <i>Computational Geometry: Theory and Applications</i>. 2017;66:28-31. doi:<a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">10.1016/j.comgeo.2017.07.002</a>","mla":"Fulek, Radoslav, et al. “On the Existence of Ordinary Triangles.” <i>Computational Geometry: Theory and Applications</i>, vol. 66, Elsevier, 2017, pp. 28–31, doi:<a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">10.1016/j.comgeo.2017.07.002</a>.","apa":"Fulek, R., Mojarrad, H., Naszódi, M., Solymosi, J., Stich, S., &#38; Szedlák, M. (2017). On the existence of ordinary triangles. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">https://doi.org/10.1016/j.comgeo.2017.07.002</a>","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."},"day":"01","main_file_link":[{"url":"https://arxiv.org/abs/1701.08183","open_access":"1"}],"page":"28 - 31","volume":66,"oa_version":"Submitted Version","project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"external_id":{"isi":["000412039700003"]},"publist_id":"6861","article_processing_charge":"No","publication":"Computational Geometry: Theory and Applications","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","department":[{"_id":"UlWa"}],"title":"On the existence of ordinary triangles","publisher":"Elsevier","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 &gt; 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"}],"ec_funded":1,"author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Mojarrad, Hossein","last_name":"Mojarrad","first_name":"Hossein"},{"last_name":"Naszódi","first_name":"Márton","full_name":"Naszódi, Márton"},{"full_name":"Solymosi, József","first_name":"József","last_name":"Solymosi"},{"last_name":"Stich","first_name":"Sebastian","full_name":"Stich, Sebastian"},{"full_name":"Szedlák, May","first_name":"May","last_name":"Szedlák"}],"date_published":"2017-01-01T00:00:00Z","_id":"793","date_created":"2018-12-11T11:48:32Z","doi":"10.1016/j.comgeo.2017.07.002","year":"2017","language":[{"iso":"eng"}],"month":"01","publication_status":"published","intvolume":"        66","type":"journal_article","date_updated":"2023-09-27T12:15:16Z"},{"publication":"Computational Geometry: Theory and Applications","article_processing_charge":"No","publist_id":"6860","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.","external_id":{"isi":["000412039700001"]},"publisher":"Elsevier","department":[{"_id":"UlWa"}],"title":"C-planarity of embedded cyclic c-graphs","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","day":"01","citation":{"apa":"Fulek, R. (2017). C-planarity of embedded cyclic c-graphs. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.comgeo.2017.06.016\">https://doi.org/10.1016/j.comgeo.2017.06.016</a>","mla":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” <i>Computational Geometry: Theory and Applications</i>, vol. 66, Elsevier, 2017, pp. 1–13, doi:<a href=\"https://doi.org/10.1016/j.comgeo.2017.06.016\">10.1016/j.comgeo.2017.06.016</a>.","ama":"Fulek R. C-planarity of embedded cyclic c-graphs. <i>Computational Geometry: Theory and Applications</i>. 2017;66:1-13. doi:<a href=\"https://doi.org/10.1016/j.comgeo.2017.06.016\">10.1016/j.comgeo.2017.06.016</a>","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.","chicago":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2017. <a href=\"https://doi.org/10.1016/j.comgeo.2017.06.016\">https://doi.org/10.1016/j.comgeo.2017.06.016</a>.","ieee":"R. Fulek, “C-planarity of embedded cyclic c-graphs,” <i>Computational Geometry: Theory and Applications</i>, vol. 66. Elsevier, pp. 1–13, 2017."},"oa":1,"quality_controlled":"1","isi":1,"oa_version":"Preprint","page":"1 - 13","volume":66,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.01346"}],"month":"12","language":[{"iso":"eng"}],"year":"2017","doi":"10.1016/j.comgeo.2017.06.016","date_updated":"2023-09-27T12:14:49Z","type":"journal_article","intvolume":"        66","publication_status":"published","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1165"}]},"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"}],"author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2018-12-11T11:48:32Z","_id":"794","scopus_import":"1","date_published":"2017-12-01T00:00:00Z"},{"quality_controlled":"1","publication_identifier":{"issn":["10778926"]},"article_number":"P3.18","day":"28","oa":1,"citation":{"ista":"Fulek R, Kynčl J, Pálvölgyi D. 2017. Unified Hanani Tutte theorem. Electronic Journal of Combinatorics. 24(3), P3.18.","apa":"Fulek, R., Kynčl, J., &#38; Pálvölgyi, D. (2017). Unified Hanani Tutte theorem. <i>Electronic Journal of Combinatorics</i>. International Press. <a href=\"https://doi.org/10.37236/6663\">https://doi.org/10.37236/6663</a>","mla":"Fulek, Radoslav, et al. “Unified Hanani Tutte Theorem.” <i>Electronic Journal of Combinatorics</i>, vol. 24, no. 3, P3.18, International Press, 2017, doi:<a href=\"https://doi.org/10.37236/6663\">10.37236/6663</a>.","ama":"Fulek R, Kynčl J, Pálvölgyi D. Unified Hanani Tutte theorem. <i>Electronic Journal of Combinatorics</i>. 2017;24(3). doi:<a href=\"https://doi.org/10.37236/6663\">10.37236/6663</a>","ieee":"R. Fulek, J. Kynčl, and D. Pálvölgyi, “Unified Hanani Tutte theorem,” <i>Electronic Journal of Combinatorics</i>, vol. 24, no. 3. International Press, 2017.","chicago":"Fulek, Radoslav, Jan Kynčl, and Dömötör Pálvölgyi. “Unified Hanani Tutte Theorem.” <i>Electronic Journal of Combinatorics</i>. International Press, 2017. <a href=\"https://doi.org/10.37236/6663\">https://doi.org/10.37236/6663</a>.","short":"R. Fulek, J. Kynčl, D. Pálvölgyi, Electronic Journal of Combinatorics 24 (2017)."},"file":[{"date_updated":"2020-07-14T12:48:06Z","date_created":"2019-01-18T14:04:08Z","checksum":"ef320cff0f062051e858f929be6a3581","access_level":"open_access","file_size":236944,"file_id":"5853","creator":"dernst","file_name":"2017_ElectrCombi_Fulek.pdf","content_type":"application/pdf","relation":"main_file"}],"oa_version":"Published Version","volume":24,"article_type":"original","publist_id":"6859","project":[{"call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme"}],"publication":"Electronic Journal of Combinatorics","article_processing_charge":"No","title":"Unified Hanani Tutte theorem","department":[{"_id":"UlWa"}],"has_accepted_license":"1","status":"public","file_date_updated":"2020-07-14T12:48:06Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"International Press","abstract":[{"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.","lang":"eng"}],"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"full_name":"Kynčl, Jan","first_name":"Jan","last_name":"Kynčl"},{"first_name":"Dömötör","last_name":"Pálvölgyi","full_name":"Pálvölgyi, Dömötör"}],"ec_funded":1,"issue":"3","date_published":"2017-07-28T00:00:00Z","scopus_import":"1","date_created":"2018-12-11T11:48:32Z","_id":"795","doi":"10.37236/6663","year":"2017","ddc":["000"],"month":"07","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"        24","type":"journal_article","date_updated":"2022-03-18T12:58:53Z"},{"author":[{"full_name":"Lubiw, Anna","first_name":"Anna","last_name":"Lubiw"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana","first_name":"Zuzana","last_name":"Masárová","orcid":"0000-0002-6660-1322"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"abstract":[{"text":"Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of O(n7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.","lang":"eng"}],"related_material":{"record":[{"id":"5986","relation":"later_version","status":"public"}]},"pubrep_id":"896","license":"https://creativecommons.org/licenses/by/4.0/","scopus_import":1,"date_published":"2017-06-01T00:00:00Z","_id":"683","conference":{"end_date":"2017-07-07","name":"SoCG: Symposium on Computational Geometry","start_date":"2017-07-04","location":"Brisbane, Australia"},"date_created":"2018-12-11T11:47:54Z","ddc":["514","516"],"year":"2017","doi":"10.4230/LIPIcs.SoCG.2017.49","language":[{"iso":"eng"}],"month":"06","intvolume":"        77","publication_status":"published","date_updated":"2023-09-05T15:01:43Z","type":"conference","quality_controlled":"1","citation":{"ista":"Lubiw A, Masárová Z, Wagner U. 2017. A proof of the orbit conjecture for flipping edge labelled triangulations. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 77, 49.","mla":"Lubiw, Anna, et al. <i>A Proof of the Orbit Conjecture for Flipping Edge Labelled Triangulations</i>. Vol. 77, 49, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">10.4230/LIPIcs.SoCG.2017.49</a>.","ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge labelled triangulations. In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">10.4230/LIPIcs.SoCG.2017.49</a>","apa":"Lubiw, A., Masárová, Z., &#38; Wagner, U. (2017). A proof of the orbit conjecture for flipping edge labelled triangulations (Vol. 77). Presented at the SoCG: Symposium on Computational Geometry, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">https://doi.org/10.4230/LIPIcs.SoCG.2017.49</a>","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge labelled triangulations,” presented at the SoCG: Symposium on Computational Geometry, Brisbane, Australia, 2017, vol. 77.","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge Labelled Triangulations,” Vol. 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">https://doi.org/10.4230/LIPIcs.SoCG.2017.49</a>.","short":"A. Lubiw, Z. Masárová, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017."},"oa":1,"day":"01","article_number":"49","alternative_title":["LIPIcs"],"tmp":{"image":"/images/cc_by.png","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)"},"volume":77,"oa_version":"Published Version","file":[{"file_size":710007,"file_name":"IST-2017-896-v1+1_LIPIcs-SoCG-2017-49.pdf","relation":"main_file","content_type":"application/pdf","creator":"system","file_id":"5265","date_created":"2018-12-12T10:17:12Z","date_updated":"2020-07-14T12:47:41Z","checksum":"24fdde981cc513352a78dcf9b0660ae9","access_level":"open_access"}],"publist_id":"7033","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:47:41Z","has_accepted_license":"1","department":[{"_id":"UlWa"}],"title":"A proof of the orbit conjecture for flipping edge labelled triangulations","status":"public","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"file":[{"file_size":990546,"file_name":"IST-2017-895-v1+1_LIPIcs-SoCG-2017-39.pdf","content_type":"application/pdf","relation":"main_file","file_id":"4856","creator":"system","date_created":"2018-12-12T10:11:03Z","date_updated":"2020-07-14T12:47:42Z","checksum":"067ab0cb3f962bae6c3af6bf0094e0f3","access_level":"open_access"}],"oa_version":"Published Version","volume":77,"page":"391-3916","tmp":{"image":"/images/cc_by.png","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)"},"alternative_title":["LIPIcs"],"day":"01","citation":{"apa":"Edelsbrunner, H., &#38; Wagner, H. (2017). Topological data analysis with Bregman divergences (Vol. 77, pp. 391–3916). Presented at the Symposium on Computational Geometry, SoCG, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">https://doi.org/10.4230/LIPIcs.SoCG.2017.39</a>","ama":"Edelsbrunner H, Wagner H. Topological data analysis with Bregman divergences. In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:391-3916. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">10.4230/LIPIcs.SoCG.2017.39</a>","mla":"Edelsbrunner, Herbert, and Hubert Wagner. <i>Topological Data Analysis with Bregman Divergences</i>. Vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 391–3916, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">10.4230/LIPIcs.SoCG.2017.39</a>.","ista":"Edelsbrunner H, Wagner H. 2017. Topological data analysis with Bregman divergences. Symposium on Computational Geometry, SoCG, LIPIcs, vol. 77, 391–3916.","short":"H. Edelsbrunner, H. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 391–3916.","ieee":"H. Edelsbrunner and H. Wagner, “Topological data analysis with Bregman divergences,” presented at the Symposium on Computational Geometry, SoCG, Brisbane, Australia, 2017, vol. 77, pp. 391–3916.","chicago":"Edelsbrunner, Herbert, and Hubert Wagner. “Topological Data Analysis with Bregman Divergences,” 77:391–3916. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">https://doi.org/10.4230/LIPIcs.SoCG.2017.39</a>."},"oa":1,"quality_controlled":"1","publication_identifier":{"issn":["18688969"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","title":"Topological data analysis with Bregman divergences","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"status":"public","has_accepted_license":"1","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:47:42Z","publist_id":"7021","date_created":"2018-12-11T11:47:56Z","conference":{"location":"Brisbane, Australia","start_date":"2017-07-04","end_date":"2017-07-07","name":"Symposium on Computational Geometry, SoCG"},"_id":"688","scopus_import":1,"date_published":"2017-06-01T00:00:00Z","pubrep_id":"895","author":[{"first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"id":"379CA8B8-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Hubert","first_name":"Hubert","last_name":"Wagner"}],"abstract":[{"text":"We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback - Leibler divergence, which is commonly used for comparing text and images, and the Itakura - Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized čech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized čech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory. ","lang":"eng"}],"date_updated":"2021-01-12T08:09:26Z","type":"conference","intvolume":"        77","publication_status":"published","month":"06","language":[{"iso":"eng"}],"year":"2017","doi":"10.4230/LIPIcs.SoCG.2017.39","ddc":["514","516"]},{"ddc":["500"],"year":"2017","language":[{"iso":"eng"}],"month":"07","intvolume":"        24","publication_status":"published","date_updated":"2021-01-12T08:11:28Z","type":"journal_article","issue":"3","abstract":[{"lang":"eng","text":"A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. For d = 2, triangular k-reptiles exist for all k of the form a^2, 3a^2 or a^2+b^2 and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, the only k-reptile simplices that are known for d ≥ 3, have k = m^d, where m is a positive integer. We substantially simplify the proof by Matoušek and the second author that for d = 3, k-reptile tetrahedra can exist only for k = m^3. We then prove a weaker analogue of this result for d = 4 by showing that four-dimensional k-reptile simplices can exist only for k = m^2."}],"author":[{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova","first_name":"Zuzana"}],"pubrep_id":"984","date_published":"2017-07-14T00:00:00Z","_id":"701","date_created":"2018-12-11T11:48:00Z","publist_id":"6996","publication":"The Electronic Journal of Combinatorics","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:47:47Z","department":[{"_id":"UlWa"}],"has_accepted_license":"1","status":"public","title":"On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4","publisher":"International Press","publication_identifier":{"issn":["10778926"]},"quality_controlled":"1","citation":{"ama":"Kynčl J, Patakova Z. On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. <i>The Electronic Journal of Combinatorics</i>. 2017;24(3):1-44.","mla":"Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices in ℝ^3 and ℝ^4.” <i>The Electronic Journal of Combinatorics</i>, vol. 24, no. 3, International Press, 2017, pp. 1–44.","apa":"Kynčl, J., &#38; Patakova, Z. (2017). On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. <i>The Electronic Journal of Combinatorics</i>. International Press.","ista":"Kynčl J, Patakova Z. 2017. On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. The Electronic Journal of Combinatorics. 24(3), 1–44.","short":"J. Kynčl, Z. Patakova, The Electronic Journal of Combinatorics 24 (2017) 1–44.","ieee":"J. Kynčl and Z. Patakova, “On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4,” <i>The Electronic Journal of Combinatorics</i>, vol. 24, no. 3. International Press, pp. 1–44, 2017.","chicago":"Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices in ℝ^3 and ℝ^4.” <i>The Electronic Journal of Combinatorics</i>. International Press, 2017."},"oa":1,"day":"14","volume":24,"page":"1-44","oa_version":"Submitted Version","file":[{"file_id":"5077","creator":"system","file_name":"IST-2018-984-v1+1_Patakova_on_the_nonexistence_of_k-reptile_simplices_in_R_3_and_R_4_2017.pdf","content_type":"application/pdf","relation":"main_file","file_size":544042,"access_level":"open_access","checksum":"a431e573e31df13bc0f66de3061006ec","date_updated":"2020-07-14T12:47:47Z","date_created":"2018-12-12T10:14:25Z"}]},{"abstract":[{"text":"We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.","lang":"eng"}],"author":[{"last_name":"Burton","first_name":"Benjamin","full_name":"Burton, Benjamin"},{"full_name":"De Mesmay, Arnaud N","first_name":"Arnaud N","last_name":"De Mesmay","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"}],"issue":"4","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"1379"}]},"scopus_import":1,"date_published":"2017-06-09T00:00:00Z","date_created":"2018-12-11T11:47:01Z","_id":"534","year":"2017","doi":"10.1007/s00454-017-9900-0","month":"06","language":[{"iso":"eng"}],"intvolume":"        58","publication_status":"published","date_updated":"2023-02-21T17:01:34Z","type":"journal_article","arxiv":1,"quality_controlled":"1","publication_identifier":{"issn":["01795376"]},"day":"09","citation":{"ista":"Burton B, de Mesmay AN, Wagner U. 2017. Finding non-orientable surfaces in 3-Manifolds. Discrete &#38; Computational Geometry. 58(4), 871–888.","apa":"Burton, B., de Mesmay, A. N., &#38; Wagner, U. (2017). Finding non-orientable surfaces in 3-Manifolds. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-017-9900-0\">https://doi.org/10.1007/s00454-017-9900-0</a>","mla":"Burton, Benjamin, et al. “Finding Non-Orientable Surfaces in 3-Manifolds.” <i>Discrete &#38; Computational Geometry</i>, vol. 58, no. 4, Springer, 2017, pp. 871–88, doi:<a href=\"https://doi.org/10.1007/s00454-017-9900-0\">10.1007/s00454-017-9900-0</a>.","ama":"Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-Manifolds. <i>Discrete &#38; Computational Geometry</i>. 2017;58(4):871-888. doi:<a href=\"https://doi.org/10.1007/s00454-017-9900-0\">10.1007/s00454-017-9900-0</a>","ieee":"B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces in 3-Manifolds,” <i>Discrete &#38; Computational Geometry</i>, vol. 58, no. 4. Springer, pp. 871–888, 2017.","chicago":"Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable Surfaces in 3-Manifolds.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00454-017-9900-0\">https://doi.org/10.1007/s00454-017-9900-0</a>.","short":"B. Burton, A.N. de Mesmay, U. Wagner, Discrete &#38; Computational Geometry 58 (2017) 871–888."},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.07907"}],"article_type":"original","oa_version":"Preprint","volume":58,"page":"871 - 888","publist_id":"7283","external_id":{"arxiv":["1602.07907"]},"publication":"Discrete & Computational Geometry","article_processing_charge":"No","title":"Finding non-orientable surfaces in 3-Manifolds","status":"public","department":[{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer"},{"doi":"10.4310/HHA.2017.v19.n2.a16","year":"2017","language":[{"iso":"eng"}],"month":"01","publication_status":"published","intvolume":"        19","type":"journal_article","date_updated":"2021-01-12T08:03:12Z","issue":"2","ec_funded":1,"abstract":[{"text":"We study robust properties of zero sets of continuous maps f: X → ℝn. Formally, we analyze the family Z&lt; r(f) := (g-1(0): ||g - f|| &lt; r) of all zero sets of all continuous maps g closer to f than r in the max-norm. All of these sets are outside A := (x: |f(x)| ≥ r) and we claim that Z&lt; r(f) is fully determined by A and an element of a certain cohomotopy group which (by a recent result) is computable whenever the dimension of X is at most 2n - 3. By considering all r &gt; 0 simultaneously, the pointed cohomotopy groups form a persistence module-a structure leading to persistence diagrams as in the case of persistent homology or well groups. Eventually, we get a descriptor of persistent robust properties of zero sets that has better descriptive power (Theorem A) and better computability status (Theorem B) than the established well diagrams. Moreover, if we endow every point of each zero set with gradients of the perturbation, the robust description of the zero sets by elements of cohomotopy groups is in some sense the best possible (Theorem C).","lang":"eng"}],"author":[{"id":"473294AE-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","last_name":"Franek","full_name":"Franek, Peter"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál","first_name":"Marek","full_name":"Krcál, Marek"}],"date_published":"2017-01-01T00:00:00Z","scopus_import":1,"_id":"568","date_created":"2018-12-11T11:47:14Z","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"},{"name":"Atomic-Resolution Structures of Mitochondrial Respiratory Chain Supercomplexes (H2020)","call_identifier":"H2020","grant_number":"701309","_id":"2590DB08-B435-11E9-9278-68D0E5697425"}],"publist_id":"7246","publication":"Homology, Homotopy and Applications","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","title":"Persistence of zero sets","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"status":"public","publisher":"International Press","publication_identifier":{"issn":["15320073"]},"quality_controlled":"1","oa":1,"citation":{"apa":"Franek, P., &#38; Krcál, M. (2017). Persistence of zero sets. <i>Homology, Homotopy and Applications</i>. International Press. <a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">https://doi.org/10.4310/HHA.2017.v19.n2.a16</a>","ama":"Franek P, Krcál M. Persistence of zero sets. <i>Homology, Homotopy and Applications</i>. 2017;19(2):313-342. doi:<a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">10.4310/HHA.2017.v19.n2.a16</a>","mla":"Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” <i>Homology, Homotopy and Applications</i>, vol. 19, no. 2, International Press, 2017, pp. 313–42, doi:<a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">10.4310/HHA.2017.v19.n2.a16</a>.","ista":"Franek P, Krcál M. 2017. Persistence of zero sets. Homology, Homotopy and Applications. 19(2), 313–342.","short":"P. Franek, M. Krcál, Homology, Homotopy and Applications 19 (2017) 313–342.","ieee":"P. Franek and M. Krcál, “Persistence of zero sets,” <i>Homology, Homotopy and Applications</i>, vol. 19, no. 2. International Press, pp. 313–342, 2017.","chicago":"Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” <i>Homology, Homotopy and Applications</i>. International Press, 2017. <a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">https://doi.org/10.4310/HHA.2017.v19.n2.a16</a>."},"day":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1507.04310"}],"page":"313 - 342","oa_version":"Submitted Version","volume":19},{"publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result","department":[{"_id":"UlWa"}],"status":"public","publication":"Israel Journal of Mathematics","project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"publist_id":"7194","acknowledgement":"The work by Z. P. was partially supported by the Israel Science Foundation grant ISF-768/12. The work by Z. P. and M. T. was partially supported by the project CE-ITI (GACR P202/12/G061) of the Czech Science Foundation and by the ERC Advanced Grant No. 267165. Part of the research work of M.T. was conducted at IST Austria, supported by an IST Fellowship. The research of P. P. was supported by the ERC Advanced grant no. 320924. The work by I. M. and U. W. was supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and SNSF-PP00P2-138948). The collaboration between U. W. and X. G. was partially supported by the LabEx Bézout (ANR-10-LABX-58).","volume":222,"page":"841 - 866","oa_version":"Preprint","main_file_link":[{"url":"https://arxiv.org/abs/1610.09063","open_access":"1"}],"citation":{"short":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, Israel Journal of Mathematics 222 (2017) 841–866.","ieee":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result,” <i>Israel Journal of Mathematics</i>, vol. 222, no. 2. Springer, pp. 841–866, 2017.","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” <i>Israel Journal of Mathematics</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s11856-017-1607-7\">https://doi.org/10.1007/s11856-017-1607-7</a>.","apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2017). On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. <i>Israel Journal of Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s11856-017-1607-7\">https://doi.org/10.1007/s11856-017-1607-7</a>","mla":"Goaoc, Xavier, et al. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” <i>Israel Journal of Mathematics</i>, vol. 222, no. 2, Springer, 2017, pp. 841–66, doi:<a href=\"https://doi.org/10.1007/s11856-017-1607-7\">10.1007/s11856-017-1607-7</a>.","ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. <i>Israel Journal of Mathematics</i>. 2017;222(2):841-866. doi:<a href=\"https://doi.org/10.1007/s11856-017-1607-7\">10.1007/s11856-017-1607-7</a>","ista":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2017. On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. Israel Journal of Mathematics. 222(2), 841–866."},"oa":1,"day":"01","quality_controlled":"1","date_updated":"2023-02-23T10:02:13Z","type":"journal_article","intvolume":"       222","publication_status":"published","language":[{"iso":"eng"}],"month":"10","year":"2017","doi":"10.1007/s11856-017-1607-7","_id":"610","date_created":"2018-12-11T11:47:29Z","scopus_import":1,"date_published":"2017-10-01T00:00:00Z","related_material":{"record":[{"id":"1511","status":"public","relation":"earlier_version"}]},"issue":"2","ec_funded":1,"author":[{"last_name":"Goaoc","first_name":"Xavier","full_name":"Goaoc, Xavier"},{"first_name":"Isaac","last_name":"Mabillard","full_name":"Mabillard, Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Pavel","last_name":"Paták","full_name":"Paták, Pavel"},{"full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova","first_name":"Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","full_name":"Tancer, Martin"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568"}],"abstract":[{"lang":"eng","text":"The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph Kn embeds in a closed surface M (other than the Klein bottle) if and only if (n−3)(n−4) ≤ 6b1(M), where b1(M) is the first Z2-Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1) embeds in R2k if and only if n ≤ 2k + 1. Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k − 1)-connected 2k-manifold with kth Z2-Betti number bk only if the following generalized Heawood inequality holds: (k+1 n−k−1) ≤ (k+1 2k+1)bk. This is a common generalization of the case of graphs on surfaces as well as the van Kampen–Flores theorem. In the spirit of Kühnel’s conjecture, we prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold with kth Z2-Betti number bk, then n ≤ 2bk(k 2k+2)+2k+4. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k−1)-connected. Our results generalize to maps without q-covered points, in the spirit of Tverberg’s theorem, for q a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition."}]},{"project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs"}],"title":"Embedding graphs into embedded graphs","department":[{"_id":"UlWa"}],"status":"public","has_accepted_license":"1","file_date_updated":"2020-07-14T12:47:33Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","article_number":"34","day":"01","oa":1,"citation":{"apa":"Fulek, R. (2017). Embedding graphs into embedded graphs (Vol. 92). Presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">https://doi.org/10.4230/LIPICS.ISAAC.2017.34</a>","mla":"Fulek, Radoslav. <i>Embedding Graphs into Embedded Graphs</i>. Vol. 92, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">10.4230/LIPICS.ISAAC.2017.34</a>.","ama":"Fulek R. Embedding graphs into embedded graphs. In: Vol 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">10.4230/LIPICS.ISAAC.2017.34</a>","ista":"Fulek R. 2017. Embedding graphs into embedded graphs. ISAAC: International Symposium on Algorithms and Computation vol. 92, 34.","short":"R. Fulek, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"R. Fulek, “Embedding graphs into embedded graphs,” presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand, 2017, vol. 92.","chicago":"Fulek, Radoslav. “Embedding Graphs into Embedded Graphs,” Vol. 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">https://doi.org/10.4230/LIPICS.ISAAC.2017.34</a>."},"tmp":{"image":"/images/cc_by.png","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)"},"file":[{"file_id":"6518","creator":"kschuh","content_type":"application/pdf","relation":"main_file","file_name":"2017_LIPIcs-Fulek.pdf","file_size":588982,"checksum":"fc7a643e29621c8bbe49d36b39081f31","access_level":"open_access","date_updated":"2020-07-14T12:47:33Z","date_created":"2019-06-04T12:20:35Z"}],"oa_version":"Published Version","volume":92,"doi":"10.4230/LIPICS.ISAAC.2017.34","year":"2017","ddc":["510"],"month":"12","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"        92","type":"conference","date_updated":"2021-01-12T08:07:51Z","author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"}],"ec_funded":1,"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"}],"date_published":"2017-12-01T00:00:00Z","scopus_import":1,"date_created":"2019-06-04T12:11:52Z","conference":{"name":"ISAAC: International Symposium on Algorithms and Computation","end_date":"2017-12-22","start_date":"2017-12-09","location":"Phuket, Thailand"},"_id":"6517"},{"type":"book_chapter","date_updated":"2024-02-28T12:59:37Z","publication_status":"published","month":"10","language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-44479-6_17","year":"2017","date_created":"2018-12-11T11:46:24Z","_id":"424","editor":[{"full_name":"Loebl, Martin","first_name":"Martin","last_name":"Loebl"},{"full_name":"Nešetřil, Jaroslav","last_name":"Nešetřil","first_name":"Jaroslav"},{"first_name":"Robin","last_name":"Thomas","full_name":"Thomas, Robin"}],"date_published":"2017-10-06T00:00:00Z","scopus_import":1,"related_material":{"record":[{"id":"1512","relation":"earlier_version","status":"public"}]},"abstract":[{"text":"We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b, d) such that the following holds. If F is a finite family of subsets of Rd such that βi(∩G)≤b for any G⊊F and every 0 ≤ i ≤ [d/2]-1 then F has Helly number at most h(b, d). Here βi denotes the reduced Z2-Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these [d/2] first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map C*(K)→C*(Rd).","lang":"eng"}],"author":[{"last_name":"Goaoc","first_name":"Xavier","full_name":"Goaoc, Xavier"},{"full_name":"Paták, Pavel","last_name":"Paták","first_name":"Pavel"},{"first_name":"Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","first_name":"Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714"},{"last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"publisher":"Springer","department":[{"_id":"UlWa"}],"status":"public","title":"Bounding helly numbers via betti numbers","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publication":"A Journey through Discrete Mathematics: A Tribute to Jiri Matousek","publist_id":"7399","page":"407 - 447","oa_version":"Published Version","main_file_link":[{"url":"https://arxiv.org/abs/1310.4613v3","open_access":"1"}],"series_title":"A Journey Through Discrete Mathematics","day":"06","oa":1,"citation":{"short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, M. Loebl, J. Nešetřil, R. Thomas (Eds.), A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, Springer, 2017, pp. 407–447.","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Bounding Helly Numbers via Betti Numbers.” In <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>, edited by Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, 407–47. A Journey Through Discrete Mathematics. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">https://doi.org/10.1007/978-3-319-44479-6_17</a>.","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding helly numbers via betti numbers,” in <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>, M. Loebl, J. Nešetřil, and R. Thomas, Eds. Springer, 2017, pp. 407–447.","ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Bounding helly numbers via betti numbers. In: Loebl M, Nešetřil J, Thomas R, eds. <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>. A Journey Through Discrete Mathematics. Springer; 2017:407-447. doi:<a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">10.1007/978-3-319-44479-6_17</a>","mla":"Goaoc, Xavier, et al. “Bounding Helly Numbers via Betti Numbers.” <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>, edited by Martin Loebl et al., Springer, 2017, pp. 407–47, doi:<a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">10.1007/978-3-319-44479-6_17</a>.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2017). Bounding helly numbers via betti numbers. In M. Loebl, J. Nešetřil, &#38; R. Thomas (Eds.), <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i> (pp. 407–447). Springer. <a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">https://doi.org/10.1007/978-3-319-44479-6_17</a>","ista":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2017.Bounding helly numbers via betti numbers. In: A Journey through Discrete Mathematics: A Tribute to Jiri Matousek. , 407–447."},"quality_controlled":"1","publication_identifier":{"isbn":["978-331944479-6"]}},{"acknowledgement":"Foremost, I would like to thank Uli Wagner for introducing me to the exciting interface between\r\ntopology and combinatorics, and for our subsequent years of fruitful collaboration.\r\nIn our creative endeavors to eliminate intersection points, we had the chance to be joined later\r\nby Sergey Avvakumov and Arkadiy Skopenkov, which led us to new surprises in dimension 12.\r\nMy stay at EPFL and IST Austria was made very agreeable thanks to all these wonderful\r\npeople: Cyril Becker, Marek Filakovsky, Peter Franek, Radoslav Fulek, Peter Gazi, Kristof Huszar,\r\nMarek Krcal, Zuzana Masarova, Arnaud de Mesmay, Filip Moric, Michal Rybar, Martin Tancer,\r\nand Stephan Zhechev.\r\nFinally, I would like to thank my thesis committee Herbert Edelsbrunner and Roman Karasev\r\nfor their careful reading of the present manuscript and for the many improvements they suggested.","publist_id":"6237","article_processing_charge":"No","department":[{"_id":"UlWa"}],"has_accepted_license":"1","status":"public","title":"Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture","file_date_updated":"2021-02-22T11:36:34Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Institute of Science and Technology Austria","publication_identifier":{"issn":["2663-337X"]},"day":"01","oa":1,"citation":{"ieee":"I. Mabillard, “Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture,” Institute of Science and Technology Austria, 2016.","chicago":"Mabillard, Isaac. “Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture.” Institute of Science and Technology Austria, 2016.","short":"I. Mabillard, Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture, Institute of Science and Technology Austria, 2016.","ista":"Mabillard I. 2016. Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture. Institute of Science and Technology Austria.","apa":"Mabillard, I. (2016). <i>Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture</i>. Institute of Science and Technology Austria.","ama":"Mabillard I. Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture. 2016.","mla":"Mabillard, Isaac. <i>Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture</i>. Institute of Science and Technology Austria, 2016."},"alternative_title":["ISTA Thesis"],"file":[{"access_level":"closed","checksum":"2d140cc924cd1b764544906fc22684ef","date_updated":"2019-08-13T08:45:27Z","date_created":"2019-08-13T08:45:27Z","file_id":"6809","creator":"dernst","file_name":"Thesis_final version_Mabillard_w_signature_page.pdf","relation":"main_file","content_type":"application/pdf","file_size":2227916},{"checksum":"2d140cc924cd1b764544906fc22684ef","access_level":"open_access","date_created":"2021-02-22T11:36:34Z","date_updated":"2021-02-22T11:36:34Z","file_name":"2016_Mabillard_Thesis.pdf","relation":"main_file","content_type":"application/pdf","file_id":"9178","creator":"dernst","success":1,"file_size":2227916}],"oa_version":"Published Version","page":"55","year":"2016","ddc":["500"],"month":"08","language":[{"iso":"eng"}],"publication_status":"published","type":"dissertation","date_updated":"2023-09-07T11:56:28Z","abstract":[{"lang":"eng","text":"Motivated by topological Tverberg-type problems  in topological combinatorics and by classical\r\nresults about embeddings (maps without double points), we study the question whether a finite\r\nsimplicial complex K  can be mapped into Rd  without triple, quadruple, or, more generally, r-fold points  (image points with at least r  distinct preimages), for a given multiplicity r ≤ 2. In particular, we are interested in maps f : K → Rd  that have no global r -fold intersection points, i.e., no r -fold points with preimages in r pairwise disjoint  simplices of K , and we seek necessary and sufficient conditions for the existence of such maps.\r\n\r\nWe present higher-multiplicity analogues of several classical results for embeddings, in particular of the completeness of the Van Kampen obstruction  for embeddability of k -dimensional\r\ncomplexes into R2k , k ≥ 3. Speciffically, we show that under suitable restrictions on the dimensions(viz., if dimK  = (r ≥ 1)k  and d  = rk \\ for some k ≥ 3), a well-known deleted product criterion (DPC ) is not only necessary but also sufficient for the existence of maps without global r -fold points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick , by which pairs of isolated r -fold points of opposite sign  can be eliminated by local modiffications of the map, assuming codimension d – dimK ≥ 3.\r\n\r\nAn important guiding idea for our work was that suffciency of the DPC, together with an old\r\nresult of Özaydin's on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the the long-standing topological Tverberg conjecture , i.e., to construct maps from the N -simplex σN  to Rd  without r-Tverberg points when r not a prime power  and\r\nN  = (d  + 1)(r – 1). Unfortunately, our proof of the sufficiency of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K  = σN .\r\n\r\nIn 2015, Frick [16] found a very elegant way to overcome this \\codimension 3 obstacle&quot; and\r\nto construct the first counterexamples to the topological Tverberg conjecture for all parameters(d; r ) with d ≥ 3r  + 1 and r  not a prime power, by a reduction1  to a suitable lower-dimensional skeleton, for which the codimension 3 restriction is satisfied and maps without r -Tverberg points exist by Özaydin's result and sufficiency of the DPC.\r\n\r\nIn this thesis, we present a different construction (which does not use the constraint method) that yields counterexamples for d ≥ 3r , r  not a prime power.     "}],"author":[{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac","first_name":"Isaac","last_name":"Mabillard"}],"supervisor":[{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"id":"2159","status":"public","relation":"part_of_dissertation"}]},"date_published":"2016-08-01T00:00:00Z","date_created":"2018-12-11T11:50:16Z","degree_awarded":"PhD","_id":"1123"},{"related_material":{"record":[{"id":"1113","status":"public","relation":"later_version"},{"relation":"earlier_version","status":"public","id":"1595"}]},"ec_funded":1,"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"last_name":"Pelsmajer","first_name":"Michael","full_name":"Pelsmajer, Michael"},{"full_name":"Schaefer, Marcus","first_name":"Marcus","last_name":"Schaefer"}],"abstract":[{"lang":"eng","text":"A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, … , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. A pair of edges e and f in a graph is independent if e and f do not share a vertex. We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing."}],"_id":"1164","conference":{"location":"Athens, Greece","start_date":"2016-09-19","name":"GD: Graph Drawing and Network Visualization","end_date":"2016-09-21"},"date_created":"2018-12-11T11:50:29Z","date_published":"2016-12-08T00:00:00Z","scopus_import":1,"language":[{"iso":"eng"}],"month":"12","doi":"10.1007/978-3-319-50106-2_36","year":"2016","type":"conference","arxiv":1,"date_updated":"2023-02-23T10:05:57Z","publication_status":"published","intvolume":"      9801","oa":1,"citation":{"chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity II,” 9801:468–81. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-50106-2_36\">https://doi.org/10.1007/978-3-319-50106-2_36</a>.","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.","short":"R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2016, 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.","apa":"Fulek, R., Pelsmajer, M., &#38; 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. <a href=\"https://doi.org/10.1007/978-3-319-50106-2_36\">https://doi.org/10.1007/978-3-319-50106-2_36</a>","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity II. In: Vol 9801. Springer; 2016:468-481. doi:<a href=\"https://doi.org/10.1007/978-3-319-50106-2_36\">10.1007/978-3-319-50106-2_36</a>","mla":"Fulek, Radoslav, et al. <i>Hanani-Tutte for Radial Planarity II</i>. Vol. 9801, Springer, 2016, pp. 468–81, doi:<a href=\"https://doi.org/10.1007/978-3-319-50106-2_36\">10.1007/978-3-319-50106-2_36</a>."},"day":"08","quality_controlled":"1","volume":9801,"page":"468 - 481","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1608.08662"}],"alternative_title":["LNCS"],"article_processing_charge":"No","project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"external_id":{"arxiv":["1608.08662"]},"publist_id":"6193","publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Hanani-Tutte for radial planarity II","department":[{"_id":"UlWa"}],"status":"public"},{"publication_status":"published","type":"conference","date_updated":"2023-09-27T12:14:48Z","doi":"10.1007/978-3-319-50106-2_8","year":"2016","language":[{"iso":"eng"}],"month":"12","date_published":"2016-12-08T00:00:00Z","scopus_import":1,"conference":{"name":"GD: Graph Drawing and Network Visualization","end_date":"2016-09-21","location":"Athens, Greece","start_date":"2016-09-19"},"_id":"1165","date_created":"2018-12-11T11:50:30Z","abstract":[{"lang":"eng","text":"We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle."}],"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","full_name":"Fulek, Radoslav"}],"ec_funded":1,"related_material":{"record":[{"status":"public","relation":"later_version","id":"794"}]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","department":[{"_id":"UlWa"}],"title":"C-planarity of embedded cyclic c-graphs","publisher":"Springer","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"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.","publist_id":"6192","main_file_link":[{"url":"https://arxiv.org/abs/1602.01346","open_access":"1"}],"alternative_title":["LNCS"],"volume":"9801 ","page":"94 - 106","oa_version":"Preprint","quality_controlled":"1","oa":1,"citation":{"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.","chicago":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs,” 9801:94–106. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-50106-2_8\">https://doi.org/10.1007/978-3-319-50106-2_8</a>.","short":"R. Fulek, in:, Springer, 2016, 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.","mla":"Fulek, Radoslav. <i>C-Planarity of Embedded Cyclic c-Graphs</i>. Vol. 9801, Springer, 2016, pp. 94–106, doi:<a href=\"https://doi.org/10.1007/978-3-319-50106-2_8\">10.1007/978-3-319-50106-2_8</a>.","ama":"Fulek R. C-planarity of embedded cyclic c-graphs. In: Vol 9801. Springer; 2016:94-106. doi:<a href=\"https://doi.org/10.1007/978-3-319-50106-2_8\">10.1007/978-3-319-50106-2_8</a>","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. <a href=\"https://doi.org/10.1007/978-3-319-50106-2_8\">https://doi.org/10.1007/978-3-319-50106-2_8</a>"},"day":"08"},{"department":[{"_id":"UlWa"}],"title":"The classification of certain linked 3-manifolds in 6-space","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Independent University of Moscow","acknowledgement":"I thank A. Skopenkov for telling me about the problem and for his useful remarks.  I also thank A. Sossinsky,\r\nA. Zhubr, M. Skopenkov, P. Akhmetiev, and an anonymous referee for their feedback.  Author was partially\r\nsupported by Dobrushin fellowship, 2013, and by RFBR grant 15-01-06302.","external_id":{"arxiv":["1408.3918"]},"publist_id":"5652","publication":"Moscow Mathematical Journal","article_processing_charge":"No","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1408.3918"}],"oa_version":"Preprint","volume":16,"page":"1 - 25","article_type":"original","quality_controlled":"1","publication_identifier":{"eissn":["1609-4514"]},"day":"01","oa":1,"citation":{"ieee":"S. Avvakumov, “The classification of certain linked 3-manifolds in 6-space,” <i>Moscow Mathematical Journal</i>, vol. 16, no. 1. Independent University of Moscow, pp. 1–25, 2016.","chicago":"Avvakumov, Sergey. “The Classification of Certain Linked 3-Manifolds in 6-Space.” <i>Moscow Mathematical Journal</i>. Independent University of Moscow, 2016. <a href=\"https://doi.org/10.17323/1609-4514-2016-16-1-1-25\">https://doi.org/10.17323/1609-4514-2016-16-1-1-25</a>.","short":"S. Avvakumov, Moscow Mathematical Journal 16 (2016) 1–25.","ista":"Avvakumov S. 2016. The classification of certain linked 3-manifolds in 6-space. Moscow Mathematical Journal. 16(1), 1–25.","apa":"Avvakumov, S. (2016). The classification of certain linked 3-manifolds in 6-space. <i>Moscow Mathematical Journal</i>. Independent University of Moscow. <a href=\"https://doi.org/10.17323/1609-4514-2016-16-1-1-25\">https://doi.org/10.17323/1609-4514-2016-16-1-1-25</a>","mla":"Avvakumov, Sergey. “The Classification of Certain Linked 3-Manifolds in 6-Space.” <i>Moscow Mathematical Journal</i>, vol. 16, no. 1, Independent University of Moscow, 2016, pp. 1–25, doi:<a href=\"https://doi.org/10.17323/1609-4514-2016-16-1-1-25\">10.17323/1609-4514-2016-16-1-1-25</a>.","ama":"Avvakumov S. The classification of certain linked 3-manifolds in 6-space. <i>Moscow Mathematical Journal</i>. 2016;16(1):1-25. doi:<a href=\"https://doi.org/10.17323/1609-4514-2016-16-1-1-25\">10.17323/1609-4514-2016-16-1-1-25</a>"},"publication_status":"published","intvolume":"        16","arxiv":1,"type":"journal_article","date_updated":"2022-02-25T10:15:57Z","doi":"10.17323/1609-4514-2016-16-1-1-25","year":"2016","month":"01","language":[{"iso":"eng"}],"date_published":"2016-01-01T00:00:00Z","scopus_import":"1","date_created":"2018-12-11T11:52:30Z","_id":"1522","abstract":[{"text":"We classify smooth Brunnian (i.e., unknotted on both components) embeddings (S2 × S1) ⊔ S3 → ℝ6. Any Brunnian embedding (S2 × S1) ⊔ S3 → ℝ6 is isotopic to an explicitly constructed embedding fk,m,n for some integers k, m, n such that m ≡ n (mod 2). Two embeddings fk,m,n and fk′ ,m′,n′ are isotopic if and only if k = k′, m ≡ m′ (mod 2k) and n ≡ n′ (mod 2k). We use Haefliger’s classification of embeddings S3 ⊔ S3 → ℝ6 in our proof. The relation between the embeddings (S2 × S1) ⊔ S3 → ℝ6 and S3 ⊔ S3 → ℝ6 is not trivial, however. For example, we show that there exist embeddings f: (S2 ×S1) ⊔ S3 → ℝ6 and g, g′ : S3 ⊔ S3 → ℝ6 such that the componentwise embedded connected sum f # g is isotopic to f # g′ but g is not isotopic to g′.","lang":"eng"}],"author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov","first_name":"Serhii","full_name":"Avvakumov, Serhii"}],"issue":"1"},{"quality_controlled":"1","citation":{"chicago":"Gundert, Anna, and Uli Wagner. “On Topological Minors in Random Simplicial Complexes.” <i>Proceedings of the American Mathematical Society</i>. American Mathematical Society, 2016. <a href=\"https://doi.org/10.1090/proc/12824\">https://doi.org/10.1090/proc/12824</a>.","ieee":"A. Gundert and U. Wagner, “On topological minors in random simplicial complexes,” <i>Proceedings of the American Mathematical Society</i>, vol. 144, no. 4. American Mathematical Society, pp. 1815–1828, 2016.","short":"A. Gundert, U. Wagner, Proceedings of the American Mathematical Society 144 (2016) 1815–1828.","ista":"Gundert A, Wagner U. 2016. On topological minors in random simplicial complexes. Proceedings of the American Mathematical Society. 144(4), 1815–1828.","mla":"Gundert, Anna, and Uli Wagner. “On Topological Minors in Random Simplicial Complexes.” <i>Proceedings of the American Mathematical Society</i>, vol. 144, no. 4, American Mathematical Society, 2016, pp. 1815–28, doi:<a href=\"https://doi.org/10.1090/proc/12824\">10.1090/proc/12824</a>.","ama":"Gundert A, Wagner U. On topological minors in random simplicial complexes. <i>Proceedings of the American Mathematical Society</i>. 2016;144(4):1815-1828. doi:<a href=\"https://doi.org/10.1090/proc/12824\">10.1090/proc/12824</a>","apa":"Gundert, A., &#38; Wagner, U. (2016). On topological minors in random simplicial complexes. <i>Proceedings of the American Mathematical Society</i>. American Mathematical Society. <a href=\"https://doi.org/10.1090/proc/12824\">https://doi.org/10.1090/proc/12824</a>"},"oa":1,"day":"01","main_file_link":[{"url":"http://arxiv.org/abs/1404.2106","open_access":"1"}],"volume":144,"page":"1815 - 1828","oa_version":"Preprint","publist_id":"5650","acknowledgement":"This research was supported by the Swiss National Science Foundation (SNF Projects 200021-125309 and 200020-138230","publication":"Proceedings of the American Mathematical Society","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","department":[{"_id":"UlWa"}],"title":"On topological minors in random simplicial complexes","publisher":"American Mathematical Society","issue":"4","abstract":[{"lang":"eng","text":"For random graphs, the containment problem considers the probability that a binomial random graph G(n, p) contains a given graph as a substructure. When asking for the graph as a topological minor, i.e., for a copy of a subdivision of the given graph, it is well known that the (sharp) threshold is at p = 1/n. We consider a natural analogue of this question for higher-dimensional random complexes Xk(n, p), first studied by Cohen, Costa, Farber and Kappeler for k = 2. Improving previous results, we show that p = Θ(1/ √n) is the (coarse) threshold for containing a subdivision of any fixed complete 2-complex. For higher dimensions k &gt; 2, we get that p = O(n−1/k) is an upper bound for the threshold probability of containing a subdivision of a fixed k-dimensional complex."}],"author":[{"last_name":"Gundert","first_name":"Anna","full_name":"Gundert, Anna"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":1,"date_published":"2016-04-01T00:00:00Z","_id":"1523","date_created":"2018-12-11T11:52:30Z","year":"2016","doi":"10.1090/proc/12824","language":[{"iso":"eng"}],"month":"04","intvolume":"       144","publication_status":"published","date_updated":"2021-01-12T06:51:22Z","type":"journal_article"},{"day":"09","citation":{"ista":"Fulek R. 2016. Bounded embeddings of graphs in the plane. IWOCA: International Workshop on Combinatorial Algorithms, LNCS, vol. 9843, 31–42.","mla":"Fulek, Radoslav. <i>Bounded Embeddings of Graphs in the Plane</i>. Vol. 9843, Springer, 2016, pp. 31–42, doi:<a href=\"https://doi.org/10.1007/978-3-319-44543-4_3\">10.1007/978-3-319-44543-4_3</a>.","ama":"Fulek R. Bounded embeddings of graphs in the plane. In: Vol 9843. Springer; 2016:31-42. doi:<a href=\"https://doi.org/10.1007/978-3-319-44543-4_3\">10.1007/978-3-319-44543-4_3</a>","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. <a href=\"https://doi.org/10.1007/978-3-319-44543-4_3\">https://doi.org/10.1007/978-3-319-44543-4_3</a>","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.","chicago":"Fulek, Radoslav. “Bounded Embeddings of Graphs in the Plane,” 9843:31–42. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-44543-4_3\">https://doi.org/10.1007/978-3-319-44543-4_3</a>.","short":"R. Fulek, in:, Springer, 2016, pp. 31–42."},"oa":1,"quality_controlled":"1","volume":9843,"oa_version":"Preprint","page":"31 - 42","alternative_title":["LNCS"],"main_file_link":[{"url":"https://arxiv.org/abs/1610.07144","open_access":"1"}],"publist_id":"5901","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"publisher":"Springer","department":[{"_id":"UlWa"}],"title":"Bounded embeddings of graphs in the plane","status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","full_name":"Fulek, Radoslav"}],"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) &lt; x(v) whenever γ(u) &lt; γ(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"}],"ec_funded":1,"date_created":"2018-12-11T11:51:31Z","conference":{"start_date":"2016-08-17","location":"Helsinki, Finland","end_date":"2018-08-19","name":"IWOCA: International Workshop on Combinatorial Algorithms"},"_id":"1348","scopus_import":1,"date_published":"2016-08-09T00:00:00Z","month":"08","language":[{"iso":"eng"}],"year":"2016","doi":"10.1007/978-3-319-44543-4_3","date_updated":"2021-01-12T06:50:03Z","type":"conference","intvolume":"      9843","publication_status":"published"},{"publist_id":"5833","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948"}],"publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing","has_accepted_license":"1","status":"public","department":[{"_id":"UlWa"}],"title":"On expansion and topological overlap","file_date_updated":"2020-07-14T12:44:47Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","day":"01","oa":1,"citation":{"chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap,” 51:35.1-35.10. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">https://doi.org/10.4230/LIPIcs.SoCG.2016.35</a>.","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA, 2016, vol. 51, p. 35.1-35.10.","short":"D. Dotterrer, T. Kaufman, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 35.1-35.10.","ista":"Dotterrer D, Kaufman T, Wagner U. 2016. On expansion and topological overlap. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 35.1-35.10.","apa":"Dotterrer, D., Kaufman, T., &#38; Wagner, U. (2016). On expansion and topological overlap (Vol. 51, p. 35.1-35.10). Presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">https://doi.org/10.4230/LIPIcs.SoCG.2016.35</a>","ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. In: Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing; 2016:35.1-35.10. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">10.4230/LIPIcs.SoCG.2016.35</a>","mla":"Dotterrer, Dominic, et al. <i>On Expansion and Topological Overlap</i>. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 35.1-35.10, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">10.4230/LIPIcs.SoCG.2016.35</a>."},"quality_controlled":"1","file":[{"file_size":536923,"creator":"system","file_id":"4699","content_type":"application/pdf","relation":"main_file","file_name":"IST-2016-623-v1+1_LIPIcs-SoCG-2016-35.pdf","date_updated":"2020-07-14T12:44:47Z","date_created":"2018-12-12T10:08:38Z","checksum":"cee65b0e722d50f9d1cc70c90ec1d59b","access_level":"open_access"}],"oa_version":"Published Version","page":"35.1 - 35.10","volume":51,"tmp":{"image":"/images/cc_by.png","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)"},"alternative_title":["LIPIcs"],"month":"06","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2016.35","year":"2016","ddc":["510"],"type":"conference","date_updated":"2023-09-27T12:29:56Z","publication_status":"published","intvolume":"        51","pubrep_id":"623","related_material":{"record":[{"relation":"later_version","status":"public","id":"742"}]},"author":[{"first_name":"Dominic","last_name":"Dotterrer","full_name":"Dotterrer, Dominic"},{"full_name":"Kaufman, Tali","first_name":"Tali","last_name":"Kaufman"},{"orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"lang":"eng","text":"We give a detailed and easily accessible proof of Gromov's Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map X → ℝd there exists a point p ∈ ℝd whose preimage intersects a positive fraction μ &gt; 0 of the d-cells of X. More generally, the conclusion holds if ℝd is replaced by any d-dimensional piecewise-linear (PL) manifold M, with a constant μ that depends only on d and on the expansion properties of X, but not on M."}],"date_created":"2018-12-11T11:51:41Z","conference":{"start_date":"2016-06-14","location":"Medford, MA, USA","name":"SoCG: Symposium on Computational Geometry","end_date":"2016-06-17"},"_id":"1378","date_published":"2016-06-01T00:00:00Z","scopus_import":1},{"intvolume":"        51","publication_status":"published","date_updated":"2023-02-23T12:23:20Z","type":"conference","ddc":["510"],"year":"2016","doi":"10.4230/LIPIcs.SoCG.2016.24","language":[{"iso":"eng"}],"month":"06","scopus_import":1,"date_published":"2016-06-01T00:00:00Z","conference":{"location":"Medford, MA, USA","start_date":"2016-06-14","end_date":"2016-06-17","name":"SoCG: Symposium on Computational Geometry"},"_id":"1379","date_created":"2018-12-11T11:51:41Z","abstract":[{"text":"We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.","lang":"eng"}],"author":[{"full_name":"Burton, Benjamin","first_name":"Benjamin","last_name":"Burton"},{"last_name":"De Mesmay","first_name":"Arnaud N","full_name":"De Mesmay, Arnaud N","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"534"}]},"pubrep_id":"622","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:44:47Z","status":"public","department":[{"_id":"UlWa"}],"title":"Finding non-orientable surfaces in 3-manifolds","has_accepted_license":"1","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing","publist_id":"5832","alternative_title":["LIPIcs"],"tmp":{"image":"/images/cc_by.png","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)"},"page":"24.1 - 24.15","volume":51,"oa_version":"Published Version","file":[{"file_size":574770,"content_type":"application/pdf","relation":"main_file","file_name":"IST-2016-622-v1+1_LIPIcs-SoCG-2016-24.pdf","creator":"system","file_id":"4930","date_created":"2018-12-12T10:12:12Z","date_updated":"2020-07-14T12:44:47Z","access_level":"open_access","checksum":"f04248a61c24297cfabd30c5f8e0deb9"}],"quality_controlled":"1","citation":{"ieee":"B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces in 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA, 2016, vol. 51, p. 24.1-24.15.","chicago":"Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable Surfaces in 3-Manifolds,” 51:24.1-24.15. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">https://doi.org/10.4230/LIPIcs.SoCG.2016.24</a>.","short":"B. Burton, A.N. de Mesmay, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 24.1-24.15.","ista":"Burton B, de Mesmay AN, Wagner U. 2016. Finding non-orientable surfaces in 3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 24.1-24.15.","mla":"Burton, Benjamin, et al. <i>Finding Non-Orientable Surfaces in 3-Manifolds</i>. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 24.1-24.15, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">10.4230/LIPIcs.SoCG.2016.24</a>.","ama":"Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-manifolds. In: Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing; 2016:24.1-24.15. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">10.4230/LIPIcs.SoCG.2016.24</a>","apa":"Burton, B., de Mesmay, A. N., &#38; Wagner, U. (2016). Finding non-orientable surfaces in 3-manifolds (Vol. 51, p. 24.1-24.15). Presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">https://doi.org/10.4230/LIPIcs.SoCG.2016.24</a>"},"oa":1,"day":"01"}]