Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!samsung!aplcen!haven!cvl!alv!sven
From: sven@alv (Sven Dickinson)
Newsgroups: comp.theory
Subject: partition into isomorphic subgraphs
Message-ID: <4355@cvl.umd.edu>
Date: 28 Feb 90 21:12:28 GMT
Sender: Unknown@cvl.umd.edu
Reply-To: sven@alv.UUCP (Sven Dickinson)
Organization: Center for Automation Research, Univ. of Md., College Park, MD 20742
Lines: 18

My apologies for the last, truncated version of my message.

There's a NP-complete problem in Garey & Johnson called "Partition
into Isomorphic Subgraphs." It states that given an instance (G,s)
where G and s are graphs, the decision problem as to whether or
not the graph G an be covered by one or more instances of graph s
(assuming no overlap) is NP-complete. The book goes on to state that
the decision problem is also NP-complete for an instance (G) where
s is a fixed graph of size >= 3.

My question is: Is the later problem also NP-complete for G and s
planar?

please send responses to sven@alv.umd.edu

Thanks,

Sven