# Z_2-Genus of graphs and minimum rank of partial symmetric matrices

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.

Download

2019_LIPIcs_Fulek.pdf
628.35 KB

*Conference Paper*|

*Published*|

*English*

**Scopus indexed**

Author

Fulek, Radoslav

^{IST Austria}^{}; Kyncl, JanDepartment

Series Title

LIPIcs

Abstract

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.

Publishing Year

Date Published

2019-06-01

Proceedings Title

35th International Symposium on Computational Geometry (SoCG 2019)

Volume

129

Article Number

39

Conference

SoCG: Symposium on Computational Geometry

Conference Location

Portland, OR, United States

Conference Date

2019-06-18 – 2019-06-21

ISBN

ISSN

IST-REx-ID

### Cite this

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.39Fulek, 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.39Fulek, 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.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.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.**All files available under the following license(s):**

**Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):**

**Main File(s)**

File Name

2019_LIPIcs_Fulek.pdf
628.35 KB

Access Level

Open Access

Date Uploaded

2020-02-04

MD5 Checksum

aac37b09118cc0ab58cf77129e691f8c

### Export

Marked PublicationsOpen Data IST Research Explorer

### Sources

arXiv 1903.08637