We study the complexity of two problems on simultaneous graph drawing. The first problem, GRACSIM DRAWING, asks for finding a simultaneous geometric embedding of two planar graphs, sharing a common subgraph, such that only crossings at right angles are allowed, and every crossing must involve a private edge of one graph and a private edge of the other graph. The second problem, k-SEFE, is a restricted version of the topological simultaneous embedding with fixed edges (SEFE) problem, for two planar graphs, in which every private edge may receive at most k crossings, where k is a prescribed positive integer. We show that GRACSIM DRAWING is NP-hard and that k-SEFE is NP-complete. The NP-hardness of both problems is proved using two similar reductions from 3-PARTITION.
On the NP-hardness of GRacSim drawing and k-SEFE Problems
Luca Grilli
2018
Abstract
We study the complexity of two problems on simultaneous graph drawing. The first problem, GRACSIM DRAWING, asks for finding a simultaneous geometric embedding of two planar graphs, sharing a common subgraph, such that only crossings at right angles are allowed, and every crossing must involve a private edge of one graph and a private edge of the other graph. The second problem, k-SEFE, is a restricted version of the topological simultaneous embedding with fixed edges (SEFE) problem, for two planar graphs, in which every private edge may receive at most k crossings, where k is a prescribed positive integer. We show that GRACSIM DRAWING is NP-hard and that k-SEFE is NP-complete. The NP-hardness of both problems is proved using two similar reductions from 3-PARTITION.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
