Fulek, Radoslav ;
Kyncl, Jan
Z_2Genus of Graphs and Minimum Rank of Partial Symmetric Matrices
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_2genus 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 2connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2genus of a graph is additive over 2connected blocks as well, and asked whether this result can be extended to socalled 2amalgamations, 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 Guv 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})=1O(1/n). Similar results are proved also for the Euler Z_2genus.
We express the Z_2genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest.
BibTeX  Entry
@InProceedings{fulek_et_al:LIPIcs:2019:10443,
author = {Radoslav Fulek and Jan Kyncl},
title = {{Z_2Genus of Graphs and Minimum Rank of Partial Symmetric Matrices}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {39:139:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10443},
URN = {urn:nbn:de:0030drops104439},
doi = {10.4230/LIPIcs.SoCG.2019.39},
annote = {Keywords: graph genus, minimum rank of a partial matrix, HananiTutte theorem, graph amalgamation}
}
11.06.2019
Keywords: 

graph genus, minimum rank of a partial matrix, HananiTutte theorem, graph amalgamation 
Seminar: 

35th International Symposium on Computational Geometry (SoCG 2019)

Issue date: 

2019 
Date of publication: 

11.06.2019 