On Some \mathcal{NP} -complete SEFE Problems

DOI10.1007/978-3-319-04657-0_20MaRDI QIDQ5746258zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Patrizio Angelini, Giordano Da Lozzo, Daniel Neuwirth

Publication date 18 February 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-04657-0_20

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3921977
• On the complexity of certain completion problems
• A note on non-complete problems in \(NP_\mathbb{R}\)
• On Unapproximable Versions of NP-Complete Problems
• On the complexity of semidefinite programs
• Complete problems for space bounded subclasses of NP
• A note on complete problems for complexity classes
• NP-completeness of the Planar Separator Problems
• DP-Complete Problems Derived from Extremal NP-Complete Properties
• Separation of NP-completeness notions

Cited in

(9)

• On strong NP-completeness of rational problems
• MPF problem over modified medial semigroup is NP-complete
• Advancements on SEFE and partitioned book embedding problems
• Simultaneous orthogonal planarity
• Simultaneous embedding of embedded planar graphs
• On the \(\mathcal{NP}\)-hardness of \textsc{GRacSim drawing} and \(k\)-SEFE problems
• Simultaneous representation of proper and unit interval graphs
• Partial and simultaneous transitive orientations via modular decompositions
• Simultaneous representation of proper and unit interval graphs

This page was built for publication: On Some $\mathcal{NP}$ -complete SEFE Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5746258)