[{"volume":129,"date_updated":"2021-01-12T08:13:24Z","date_created":"2020-01-29T16:17:05Z","author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav"},{"first_name":"Jan","last_name":"Kyncl","full_name":"Kyncl, Jan"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2019","license":"https://creativecommons.org/licenses/by/4.0/","file_date_updated":"2020-07-14T12:47:57Z","article_number":"39","language":[{"iso":"eng"}],"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"},"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":["1903.08637"]},"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,"publication_identifier":{"isbn":["978-3-95977-104-7"],"issn":["1868-8969"]},"month":"06","oa_version":"Published Version","file":[{"creator":"dernst","content_type":"application/pdf","file_size":628347,"file_name":"2019_LIPIcs_Fulek.pdf","access_level":"open_access","date_updated":"2020-07-14T12:47:57Z","date_created":"2020-02-04T09:14:31Z","checksum":"aac37b09118cc0ab58cf77129e691f8c","file_id":"7445","relation":"main_file"}],"intvolume":" 129","status":"public","ddc":["000"],"title":"Z_2-Genus of graphs and minimum rank of partial symmetric matrices","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7401","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"}],"alternative_title":["LIPIcs"],"type":"conference","date_published":"2019-06-01T00:00:00Z","citation":{"short":"R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","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.","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.","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","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","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."},"publication":"35th International Symposium on Computational Geometry (SoCG 2019)","article_processing_charge":"No","has_accepted_license":"1","day":"01","scopus_import":1},{"file_date_updated":"2020-07-14T12:47:33Z","year":"2019","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"8032"}]},"author":[{"full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár","first_name":"Kristóf"},{"first_name":"Jonathan","last_name":"Spreer","full_name":"Spreer, Jonathan"}],"volume":129,"date_updated":"2023-09-07T13:18:26Z","date_created":"2019-06-11T20:09:57Z","publication_identifier":{"isbn":["978-3-95977-104-7"],"issn":["1868-8969"]},"month":"06","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"},"external_id":{"arxiv":["1812.05528"]},"oa":1,"quality_controlled":"1","doi":"10.4230/LIPIcs.SoCG.2019.44","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2019-06-21","location":"Portland, Oregon, United States","start_date":"2019-06-18"},"language":[{"iso":"eng"}],"type":"conference","alternative_title":["LIPIcs"],"abstract":[{"text":"Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6556","intvolume":" 129","title":"3-manifold triangulations with small treewidth","ddc":["516"],"status":"public","file":[{"date_created":"2019-06-12T06:45:33Z","date_updated":"2020-07-14T12:47:33Z","checksum":"29d18c435368468aa85823dabb157e43","relation":"main_file","file_id":"6557","file_size":905885,"content_type":"application/pdf","creator":"kschuh","file_name":"2019_LIPIcs-Huszar.pdf","access_level":"open_access"}],"oa_version":"Published Version","scopus_import":"1","keyword":["computational 3-manifold topology","fixed-parameter tractability","layered triangulations","structural graph theory","treewidth","cutwidth","Heegaard genus"],"has_accepted_license":"1","article_processing_charge":"No","day":"01","citation":{"ista":"Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 44:1-44:20.","apa":"Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small treewidth. In 35th International Symposium on Computational Geometry (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44","ieee":"K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in 35th International Symposium on Computational Geometry, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20.","ama":"Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44","chicago":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In 35th International Symposium on Computational Geometry, 129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44.","mla":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44.","short":"K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20."},"publication":"35th International Symposium on Computational Geometry","page":"44:1-44:20","date_published":"2019-06-01T00:00:00Z"}]