On the \mathcal{NP}-hardness of GRacSim Drawing and k-SEFE Problems
Grilli · cs.CG,cs.CC · 2016-11-13 · 原文
We study the complexity of two problems in simultaneous graph drawing. The first problem, GRacSim Drawing, asks for finding a simultaneous geometric embedding of two graphs such that only crossings at right angles are allowed. 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 \mathcal{NP}-hard and that k-SEFE is \mathcal{NP}-complete. The \mathcal{NP}-hardness of both problems is proved using two similar reductions from 3-Partition.
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
We study the complexity of two problems in simultaneous graph drawing.
The first problem, GRacSim Drawing, asks for finding a simultaneous geometric embedding of two graphs such that only crossings at right angles are allowed.
2. 领域脉络
本文类目：cs.CG、cs.CC，属于其所在研究脉络的最新进展。
3. 机制拆解
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 \mathcal{NP}-hard and that k-SEFE is \mathcal{NP}-complete.
4. 证据与数字
The \mathcal{NP}-hardness of both problems is proved using two similar reductions from 3-Partition.
5. 反例与边界
摘要未声明局限与反例——这是需要警惕的信号，精读时先问边界。
6. 跨领域连接与意外收获
横跨 2 个类目（cs.CG、cs.CC），关注其在你兴趣板块间的迁移面。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。