00704654

j

00704654 \v{Z}itnik, Arjana Drawing graphs on surfaces. SIAM J. Discrete Math. 7, No.4, 593-597 (1994). 1994 Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA EN graph drawing algorithm 2-cell embedding surface genus fundamental polygon embedding disjoint paths problem

doi:10.1137/S0895480192242006

Suppose that we have a 2-cell embedding of a graph $G$ in an orientable surface $S\sb g$ of genus $g$. The surface can be represented by the standard fundamental polygon that is a convex $(4g)$-gon in the plane with its sides pairwise identified as $a\sb 1 b\sb 1 a\sp -\sb 1 b\sp - \sb 1\cdots a\sb g b\sb g a\sp -\sb g b\sp -\sb g$. It is shown that the problem of representing the embedding of $G$ in the standard polygon such that all vertices are inside the polygon and each of the edges crosses at most one of the identified sides can be reduced to the $k$ disjoint paths problem $(k= 2g)$ that is polynomially solvable for fixed $g$; see {\it N. Robertson} and {\it P. D. Seymour} [Graph minors. XIII: The disjoint paths problem, J. Comb. Theory, Ser. B 63, 65-110 (1995)]. B.Mohar (Ljubljana)