Browse Prior Art Database

THE COMPLEXITY OF EXTENDING A GRAPH IMBEDDING

IP.com Disclosure Number: IPCOM000128624D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 19 page(s) / 42K

Publishing Venue

Software Patent Institute

Related People

John H. Reif: AUTHOR [+3]

Abstract

Given a graph G and an imbedding 10 of a subgraph Go of G into a --2=manifold M, the imbedding extension problem is to determine if there exists an imbedding I of G into M extending Io. We show that this problem is complete in nondeterministic polynomial time, even if (1) G is cubic (the maximum valence of any vertex of G is 3), or (2) Io is guasiplanar (each closed face of Io is homeomorphic to a disk). This complexity result is tight in the sense that if G is cubic and Io is quasiplanar, then the imbedding extension problem can be solved in quadratic time. We also show that the problem of counting nonisotopic imbeddings of a cubic graph extending a given quasiplanar imbedding is a complete counting problem.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 19

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE COMPLEXITY OF EXTENDING A GRAPH IMBEDDING

John H. Reif

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

Abstract

Given a graph G and an imbedding 10 of a subgraph Go of G into a --2=manifold M, the imbedding extension problem is to determine if there exists an imbedding I of G into M extending Io. We show that this problem is complete in nondeterministic polynomial time, even if
(1) G is cubic (the maximum valence of any vertex of G is 3), or (2) Io is guasiplanar (each closed face of Io is homeomorphic to a disk). This complexity result is tight in the sense that if G is cubic and Io is quasiplanar, then the imbedding extension problem can be solved in quadratic time. We also show that the problem of counting nonisotopic imbeddings of a cubic graph extending a given quasiplanar imbedding is a complete counting problem.

1. Introduction

Considerable research effort CLempel, Even, and Cederbaum, 1967; Nopcroft and Tarjan, 1974] has been devoted to efficient algorithms for recognition of planar graphs: graphs which have an imbedding into the plane. In general, the imbedding problem for graph G and topological surface M is to determine if G has an imbedding into M. We have recently [Reif, 1978] developed a polynomial-time algorithm for the imbedding problem for any fixed orientable surface. Our algorithm for the imbedding problem and many previous algorithms (for example, the CHopcroft and Tarjan, 1974] planar graph recognition algorithm arid the LFilotti, 1978a and 1978bJ cubic, toroidal graph recognition algorithm) have the following general form: (1) Initially we construct a fixed number of imbeddings of subgraphs of graph G into surface M. Next, we attempt to extend each of these partial imbeddings to an imbedding of G into M. This paper is concerned with the time complexity of the imbedding extension problem: given a graph G and an imbedding IQ of a subgraph of G into surface M, determine if G has an imbedding into M extending Io. We have shown [Reif, 1978] that if the surface M is fixed and orientable, then the imbedding extension problem is in polynomial time. Unfortunately, we show here that the imbedding extension problem for arbitrary surfaces is NP-complete in the sense of [Cook, 1971]. This implies that the imbedding problem for graph G and arbitrary surface M cannot be solved efficiently by an algorithm of the above form, unless P = NP. _2_

In the next section we give some preliminary definitions on computational complexity, surfaces, graphs and their imbeddings into surfaces. Section 3 presents our proof that the imbedding extension problem is NP-complete. Section 4 gives a polynomial-time algorithm for solving a restricted class of imbedding extension problems. Section 5 concludes the paper with some related open problems.

2. P...