Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!mcgill-vision!bloom-beacon!snorkelwacker!usc!brutus.cs.uiuc.edu!ux1.cso.uiuc.edu!tank!mimsy!cvl!Unknown
From: Unknown@cvl.umd.edu (Unknown)
Newsgroups: comp.theory
Subject: partition into isomorphic subgraphs
Message-ID: <4354@cvl.umd.edu>
Date: 28 Feb 90 19:04:47 GMT
Reply-To: sven@alv.UUCP (Sven Dickinson)
Organization: Center for Automation Research, Univ. of Md., College Park, MD 20742
Lines: 17

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.
From: sven@alv (Sven Dickinson)
Path: alv!sven

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