---
_id: '7401'
abstract:
- lang: eng
  text: 'The genus g(G) of a graph G is the minimum g such that G has an embedding
    on the orientable surface M_g of genus g. A drawing of a graph on a surface is
    independently even if every pair of nonadjacent edges in the drawing crosses an
    even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum
    g such that G has an independently even drawing on M_g. By a result of Battle,
    Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected
    blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph
    is additive over 2-connected blocks as well, and asked whether this result can
    be extended to so-called 2-amalgamations, as an analogue of results by Decker,
    Glover, Huneke, and Stahl for the genus. We give the following partial answer.
    If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has
    k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1.
    For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n).
    Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus
    of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem
    that might be of independent interest. '
alternative_title:
- LIPIcs
article_number: '39'
article_processing_charge: No
arxiv: 1
author:
- first_name: Radoslav
  full_name: Fulek, Radoslav
  id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
  last_name: Fulek
  orcid: 0000-0001-8485-1774
- first_name: Jan
  full_name: Kyncl, Jan
  last_name: Kyncl
citation:
  ama: 'Fulek R, Kyncl J. Z_2-Genus of graphs and minimum rank of partial symmetric
    matrices. In: <i>35th International Symposium on Computational Geometry (SoCG
    2019)</i>. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:<a
    href="https://doi.org/10.4230/LIPICS.SOCG.2019.39">10.4230/LIPICS.SOCG.2019.39</a>'
  apa: 'Fulek, R., &#38; Kyncl, J. (2019). Z_2-Genus of graphs and minimum rank of
    partial symmetric matrices. In <i>35th International Symposium on Computational
    Geometry (SoCG 2019)</i> (Vol. 129). Portland, OR, United States: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.SOCG.2019.39">https://doi.org/10.4230/LIPICS.SOCG.2019.39</a>'
  chicago: Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of
    Partial Symmetric Matrices.” In <i>35th International Symposium on Computational
    Geometry (SoCG 2019)</i>, Vol. 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2019. <a href="https://doi.org/10.4230/LIPICS.SOCG.2019.39">https://doi.org/10.4230/LIPICS.SOCG.2019.39</a>.
  ieee: R. Fulek and J. Kyncl, “Z_2-Genus of graphs and minimum rank of partial symmetric
    matrices,” in <i>35th International Symposium on Computational Geometry (SoCG
    2019)</i>, Portland, OR, United States, 2019, vol. 129.
  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.'
  mla: Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial
    Symmetric Matrices.” <i>35th International Symposium on Computational Geometry
    (SoCG 2019)</i>, vol. 129, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2019, doi:<a href="https://doi.org/10.4230/LIPICS.SOCG.2019.39">10.4230/LIPICS.SOCG.2019.39</a>.
  short: R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry
    (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
conference:
  end_date: 2019-06-21
  location: Portland, OR, United States
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2019-06-18
date_created: 2020-01-29T16:17:05Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2021-01-12T08:13:24Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.4230/LIPICS.SOCG.2019.39
external_id:
  arxiv:
  - '1903.08637'
file:
- access_level: open_access
  checksum: aac37b09118cc0ab58cf77129e691f8c
  content_type: application/pdf
  creator: dernst
  date_created: 2020-02-04T09:14:31Z
  date_updated: 2020-07-14T12:47:57Z
  file_id: '7445'
  file_name: 2019_LIPIcs_Fulek.pdf
  file_size: 628347
  relation: main_file
file_date_updated: 2020-07-14T12:47:57Z
has_accepted_license: '1'
intvolume: '       129'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: M02281
  name: Eliminating intersections in drawings of graphs
publication: 35th International Symposium on Computational Geometry (SoCG 2019)
publication_identifier:
  isbn:
  - 978-3-95977-104-7
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Z_2-Genus of graphs and minimum rank of partial symmetric matrices
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...
---
_id: '6556'
abstract:
- lang: eng
  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.'
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Kristóf
  full_name: Huszár, Kristóf
  id: 33C26278-F248-11E8-B48F-1D18A9856A87
  last_name: Huszár
  orcid: 0000-0002-5445-5057
- first_name: Jonathan
  full_name: Spreer, Jonathan
  last_name: Spreer
citation:
  ama: 'Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: <i>35th
    International Symposium on Computational Geometry</i>. Vol 129. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">10.4230/LIPIcs.SoCG.2019.44</a>'
  apa: 'Huszár, K., &#38; Spreer, J. (2019). 3-manifold triangulations with small
    treewidth. In <i>35th International Symposium on Computational Geometry</i> (Vol.
    129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>'
  chicago: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
    Treewidth.” In <i>35th International Symposium on Computational Geometry</i>,
    129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>.
  ieee: K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,”
    in <i>35th International Symposium on Computational Geometry</i>, Portland, Oregon,
    United States, 2019, vol. 129, p. 44:1-44:20.
  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.'
  mla: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
    Treewidth.” <i>35th International Symposium on Computational Geometry</i>, vol.
    129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:<a
    href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">10.4230/LIPIcs.SoCG.2019.44</a>.
  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.
conference:
  end_date: 2019-06-21
  location: Portland, Oregon, United States
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2019-06-18
date_created: 2019-06-11T20:09:57Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T13:18:26Z
day: '01'
ddc:
- '516'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2019.44
external_id:
  arxiv:
  - '1812.05528'
file:
- access_level: open_access
  checksum: 29d18c435368468aa85823dabb157e43
  content_type: application/pdf
  creator: kschuh
  date_created: 2019-06-12T06:45:33Z
  date_updated: 2020-07-14T12:47:33Z
  file_id: '6557'
  file_name: 2019_LIPIcs-Huszar.pdf
  file_size: 905885
  relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: '       129'
keyword:
- computational 3-manifold topology
- fixed-parameter tractability
- layered triangulations
- structural graph theory
- treewidth
- cutwidth
- Heegaard genus
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 44:1-44:20
publication: 35th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - 978-3-95977-104-7
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '8032'
    relation: part_of_dissertation
    status: public
scopus_import: '1'
status: public
title: 3-manifold triangulations with small treewidth
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...