[comp.theory] partition into isomorphic subgraphs

Unknown@cvl.umd.edu (Unknown) (03/01/90)

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

sven@alv (Sven Dickinson) (03/01/90)

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