2019/03/20 by Radoslav Fulek, Fulek, Radoslav, Jan Kynčl +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CG #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1903.08637
Extended version (preliminary abstract accepted in the proceedings of SoCG 2019)
arxiv created 2019/03/20 · arxiv updated 2019/03/21
The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface Mg 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 \emphℤ2-genus of a graph G, denoted by g0(G), is the minimum g such that G has an independently even drawing on Mg. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Štefankovič proved that the ℤ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=G1∪ G2, G1 and G2 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 |g0(G)-(g0(G1)+g0(G2))|≤ k+1. For complete bipartite graphs Km,n, with n≥ m≥ 3, we prove that \fracg0(Km,n)g(Km,n)=1-O((1)/(n)). Similar results are proved also for the Euler ℤ2-genus. We express the ℤ2-genus of a graph using the minimum rank of partial symmetric matrices over ℤ2; a problem that might be of independent interest.