# POLYNOMIAL TIME RECOGNITION OF GRAPHS OF FIXED GENUS

Original Publication Date: 1978-Dec-31

Included in the Prior Art Database: 2005-Sep-16

## Publishing Venue

Software Patent Institute

## Related People

John H. Reif: AUTHOR [+3]

## Abstract

By a surface we mean an orientable 2-manifold. Surfaces are classified by their genus; a sphere has genus 0, a torus has genus 1, and in general a surface of genus Y >0 has y "handles." The genus of a graph G is the lowest integer y > 0 such that there is an imbedding of G into a surface of genus Y. A number of linear-time algorithms exist for recognition of planar graphs. The best-known previous algorithm for recognition of graphs of some fixed genus Y > 0 runs in exponential time, although CF'i.lotti, 19?8a and b3 has a polynomial-time algorithm for recognition of cubic graphs of genus I. The primary result of this paper is for any [Equation ommitted] time algorithm for recognition of graphs of genus y, where ci, c2 are fixed constants. Our algorithms are constructive yielding an imbedding of a graph of genus Y into a surface of genus -y. This paper is organized as follows: the second section is an elementary introduction to topological surfaces; Section 3 defines our graph terminology; and Section 4 defines graph imbeddings. Section 5 describes the well-known exponential-time graph imbedding algorithm, often known as Edmond's Algorithm. Section 6 describes an efficient, simple method due to Gary Miller for constructing a partial imbedding of a graph G into a surface of fixed genus y. The resulting imbedded subgraph of G is homeomorphic to a graph of size linear in Y. The Sections 7 through 12 are concerned with extending a partial imbedding. Section 7 defines pieces, which are certain yet-to-be-imbedded connected portions of partially imbedded graphs. Section 8 describes a linear-time algorithm for extending a restricted class of partial graph imbeddings, called simple. Section 9 defines an equivalence relation on pieces. Sections 10 and 11 characterize imbeddings of certain classes of pieces. Section 12 describes our polynomial-time algorithm for extending a partial graph imbedding in which the imbedded subgraph is homeomorphic to a graph of fixed size. Section 13 concludes the paper.

**This text was extracted from a PDF file.**

**This is the abbreviated version, containing approximately 9% of the total text.**

__Page 1 of 39__THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

**POLYNOMIAL TIME RECOGNITION OF GRAPHS OF FIXED GENUS **

John H. Reif

Computer Science Department University of Rochester TR33 October 1978 The preparation of this paper was supported in part by the Alfred P. Sloan Foundation under grant 74-12-5.

Polynomial Time Recognition of Graphs of Fixed Genus

John H. Reif

**1. Introduction **

By a surface we mean an orientable 2-manifold. Surfaces are classified by their genus; a sphere has genus 0, a torus has genus 1, and in general a surface of genus Y >0 has y "handles." The genus of a graph G is the lowest integer y > 0 such that there is an imbedding of G into a surface of genus Y. A number of linear-time algorithms exist for recognition of planar graphs. The best-known previous algorithm for recognition of graphs of some fixed genus Y > 0 runs in exponential time, although CF'i.lotti, 19?8a and b3 has a polynomial-time algorithm for recognition of cubic graphs of genus I. The primary result of this paper is for any

(Equation Omitted)

time algorithm for recognition of graphs of genus y, where ci, c2 are fixed constants. Our algorithms are constructive yielding an imbedding of a graph of genus Y into a surface of genus -y. This paper is organized as follows: the second section is an elementary introduction to topological surfaces; Section 3 defines our graph terminology; and Section 4 defines graph imbeddings. Section 5 describes the well-known exponential-time graph imbedding algorithm, often known as Edmond's Algorithm. Section 6 describes an efficient, simple method due to Gary Miller for constructing a partial imbedding of a graph G into a surface of fixed genus y. The resulting imbedded subgraph of G is homeomorphic to a graph of size linear in Y. The Sections 7 through 12 are concerned with extending a partial imbedding. Section 7 defines pieces, which are certain yet-to-be-imbedded

connected portions of partially imbedded graphs. Section 8 describes a linear-time algorithm for extending a restricted class of partial graph imbeddings, called simple. Section 9 defines an equivalence relation on pieces. Sections 10 and 11 characterize imbeddings of certain classes of pieces. Section 12 describes our polynomial-time algorithm for extending a partial graph imbedding in which the imbedded subgraph is homeomorphic to a graph of fixed size. Section 13 concludes the paper.

**2. Topological Surfaces **

An open disk is a set of points

(Equation Omitted)

Columbia University Page 1 Dec 31, 1978

__Page 2 of 39__POLYNOMIAL TIME RECOGNITION OF GRAPHS OF FIXED GENUS

for some

(Equation Omitted)

-manifold is a connected topological space M in which each point has a neighborhood homeomorphic to an open disk. For our purposes, M may be considered a subspace of Euclidean 3-space. M is orientable if, for each simple closed curve C in M, a clockwise sense of rotation is preserved by traveling once around C. The projective plane, Mobius strip, and Klein bot...