Can I read Deepening the Relationship between SEFE and C-Planarity on EtoBox?

Deepening the Relationship between SEFE and C-Planarity by Angelini, Patrizio; Da Lozzo, Giordano is a scholarly article available to read on EtoBox.

What is Deepening the Relationship between SEFE and C-Planarity about?

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.

Author

Angelini, Patrizio; Da Lozzo, Giordano

Published

2014

Language

EN