Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Graph Drawing Beyond Planarity
DOI: 10.7155/jgaa.00456
On the NPhardness of GRacSim drawing and kSEFE Problems
Luca Grilli
Vol. 22, no. 1, pp. 101116, 2018. Regular paper.
Abstract We study the complexity of two problems on simultaneous graph drawing.
The first problem, $\rm{GR{\small AC} S{\small IM~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\rm{SEFE}$, is a restricted version of the topological simultaneous embedding with fixed edges ($\rm{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 $\rm{GR{\small AC} S{\small IM~DRAWING}}$ is $\mathcal{NP}$hard and that $k\rm{SEFE}$ is $\mathcal{NP}$complete.
The $\mathcal{NP}$hardness of both problems is proved using two similar reductions from $\rm{3P\small{ARTITION}}$.

Submitted: May 2017.
Reviewed: July 2017.
Revised: August 2017.
Accepted: October 2017.
Final: October 2017.
Published: January 2018.
