The QuaSEFE Problem

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

doi:10.1007/978-3-030-35802-0_21

The QuaSEFE Problem

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

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 language	English (US)
Title of host publication	Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings
Editors	Daniel Archambault, Csaba D. Tóth
Publisher	Springer
Pages	268-275
Number of pages	8
ISBN (Print)	9783030358013
DOIs	https://doi.org/10.1007/978-3-030-35802-0_21
State	Published - 2019
Event	27th International Symposium on Graph Drawing and Network Visualization, GD 2019 - Prague, Czech Republic Duration: Sep 17 2019 → Sep 20 2019

Publication series

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

Conference

Conference	27th International Symposium on Graph Drawing and Network Visualization, GD 2019
Country/Territory	Czech Republic
City	Prague
Period	9/17/19 → 9/20/19

Keywords

Quasiplanar
SEFE
Simultaneous graph drawing

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-35802-0_21

Cite this

Angelini, P., Förster, H., Hoffmann, M., Kaufmann, M., Kobourov, S., Liotta, G., & Patrignani, M. (2019). The QuaSEFE Problem. In D. Archambault, & C. D. Tóth (Eds.), Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings (pp. 268-275). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11904 LNCS). Springer. https://doi.org/10.1007/978-3-030-35802-0_21

The QuaSEFE Problem. / Angelini, Patrizio; Förster, Henry; Hoffmann, Michael et al.
Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings. ed. / Daniel Archambault; Csaba D. Tóth. Springer, 2019. p. 268-275 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11904 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Angelini, P, Förster, H, Hoffmann, M, Kaufmann, M, Kobourov, S, Liotta, G & Patrignani, M 2019, The QuaSEFE Problem. in D Archambault & CD Tóth (eds), Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11904 LNCS, Springer, pp. 268-275, 27th International Symposium on Graph Drawing and Network Visualization, GD 2019, Prague, Czech Republic, 9/17/19. https://doi.org/10.1007/978-3-030-35802-0_21

Angelini P, Förster H, Hoffmann M, Kaufmann M, Kobourov S, Liotta G et al. The QuaSEFE Problem. In Archambault D, Tóth CD, editors, Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings. Springer. 2019. p. 268-275. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-35802-0_21

Angelini, Patrizio ; Förster, Henry ; Hoffmann, Michael et al. / The QuaSEFE Problem. Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings. editor / Daniel Archambault ; Csaba D. Tóth. Springer, 2019. pp. 268-275 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b757c371c7cc4c6c89d6f581a4644597,

title = "The QuaSEFE Problem",

abstract = "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.",

keywords = "Quasiplanar, SEFE, Simultaneous graph drawing",

author = "Patrizio Angelini and Henry F{\"o}rster and Michael Hoffmann and Michael Kaufmann and Stephen Kobourov and Giuseppe Liotta and Maurizio Patrignani",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 27th International Symposium on Graph Drawing and Network Visualization, GD 2019 ; Conference date: 17-09-2019 Through 20-09-2019",

year = "2019",

doi = "10.1007/978-3-030-35802-0_21",

language = "English (US)",

isbn = "9783030358013",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "268--275",

editor = "Daniel Archambault and T{\'o}th, {Csaba D.}",

booktitle = "Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings",

}

TY - GEN

T1 - The QuaSEFE Problem

AU - Angelini, Patrizio

AU - Förster, Henry

AU - Hoffmann, Michael

AU - Kaufmann, Michael

AU - Kobourov, Stephen

AU - Liotta, Giuseppe

AU - Patrignani, Maurizio

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2019.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Quasiplanar

KW - SEFE

KW - Simultaneous graph drawing

UR - http://www.scopus.com/inward/record.url?scp=85076910884&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85076910884&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-35802-0_21

DO - 10.1007/978-3-030-35802-0_21

M3 - Conference contribution

AN - SCOPUS:85076910884

SN - 9783030358013

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 268

EP - 275

BT - Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings

A2 - Archambault, Daniel

A2 - Tóth, Csaba D.

PB - Springer

T2 - 27th International Symposium on Graph Drawing and Network Visualization, GD 2019

Y2 - 17 September 2019 through 20 September 2019

ER -

The QuaSEFE Problem

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this