The QuaSEFE Problem

Patrizio Angelini, Henry Förster, Michael Hoffmann, Michael Kaufmann, Stephen Kobourov, Giuseppe Liotta, Maurizio Patrignani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QuaSEFE problem, we allow edge crossings, as long as each graph individually is drawn quasiplanar, that is, no three edges pairwise cross. We show that a triple consisting of two planar graphs and a tree admit a QuaSEFE. This result also implies that a pair consisting of a 1-planar graph and a planar graph admits a QuaSEFE. We show several other positive results for triples of planar graphs, in which certain structural properties for their common subgraphs are fulfilled. For the case in which simplicity is also required, we give a triple consisting of two quasiplanar graphs and a star that does not admit a QuaSEFE. Moreover, in contrast to the planar SEFE problem, we show that it is not always possible to obtain a QuaSEFE for two matchings if the quasiplanar drawing of one matching is fixed.

Original languageEnglish (US)
Title of host publicationGraph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings
EditorsDaniel Archambault, Csaba D. Tóth
Number of pages8
ISBN (Print)9783030358013
StatePublished - 2019
Event27th International Symposium on Graph Drawing and Network Visualization, GD 2019 - Prague, Czech Republic
Duration: Sep 17 2019Sep 20 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11904 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Symposium on Graph Drawing and Network Visualization, GD 2019
Country/TerritoryCzech Republic


  • Quasiplanar
  • SEFE
  • Simultaneous graph drawing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'The QuaSEFE Problem'. Together they form a unique fingerprint.

Cite this