Generalized Thrackle Drawings of Non-bipartite Graphs |
| |
Authors: | Grant Cairns Yury Nikolayevsky |
| |
Affiliation: | (1) Department of Mathematics, La Trobe University, Melbourne, Australia, 3086 |
| |
Abstract: | A graph drawing is called a generalized thrackle if every pair of edges meets an odd number of times. In a previous paper, we showed that a bipartite graph G can be drawn as a generalized thrackle on an oriented closed surface M if and only if G can be embedded in M. In this paper, we use Lins’ notion of a parity embedding and show that a non-bipartite graph can be drawn as a generalized thrackle on an oriented closed surface M if and only if there is a parity embedding of G in a closed non-orientable surface of Euler characteristic χ(M)−1. As a corollary, we prove a sharp upper bound for the number of edges of a simple generalized thrackle. |
| |
Keywords: | Graph drawing Thrackle |
本文献已被 SpringerLink 等数据库收录! |
|