Pith. sign in

REVIEW 1 cited by

Deepening the Relationship between SEFE and C-Planarity

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1404.6175 v1 pith:YB62Y7QZ submitted 2014-04-24 cs.CC cs.DS

Patrizio Angelini , Giordano Da Lozzo This is my paper · ORCID
classification cs.CCcs.DS
keywords c-planaritysefegraphopenproblemsreductionsefe-2clustered
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

In this paper we deepen the understanding of the connection between two long-standing Graph Drawing open problems, that is, Simultaneous Embedding with Fixed Edges (SEFE) and Clustered Planarity (C-PLANARITY). In his GD'12 paper Marcus Schaefer presented a reduction from C-PLANARITY to SEFE of two planar graphs (SEFE-2). We prove that a reduction exists also in the opposite direction, if we consider instances of SEFE-2 in which the intersection graph is connected. We pose as an open question whether the two problems are polynomial-time equivalent.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Monotone Clustered Level Planarity

    cs.DS 2026-07 conditional novelty 7.0 of 10

    mCLP is NP-complete even on constant-size-tree forests with bounded levels or clusters, and FPT when parameterized by vertex cover number plus number of clusters.

Pith tools