We show that every n-vertex planar graph admits a simultaneous embedding without mapping and with fixed edges with any inline image-vertex planar graph. In order to achieve this result, we prove that every n-vertex plane graph has an induced outerplane subgraph containing at least inline image vertices. Also, we show that every n-vertex planar graph and every n-vertex planar partial 3-tree admit a simultaneous embedding without mapping and with fixed edges.

Angelini, P., Evans, W., Frati, F., & Gudmundsson, J. (2016). SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs. JOURNAL OF GRAPH THEORY, 82(1), 45-64 [10.1002/jgt.21884].

SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs

ANGELINI, PATRIZIO;FRATI, FABRIZIO;
2016

Abstract

We show that every n-vertex planar graph admits a simultaneous embedding without mapping and with fixed edges with any inline image-vertex planar graph. In order to achieve this result, we prove that every n-vertex plane graph has an induced outerplane subgraph containing at least inline image vertices. Also, we show that every n-vertex planar graph and every n-vertex planar partial 3-tree admit a simultaneous embedding without mapping and with fixed edges.
Angelini, P., Evans, W., Frati, F., & Gudmundsson, J. (2016). SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs. JOURNAL OF GRAPH THEORY, 82(1), 45-64 [10.1002/jgt.21884].
File in questo prodotto:
File Dimensione Formato  
InducedOuterplanePlaneGraphs.pdf

accesso aperto

Descrizione: Published version at https://doi.org/10.1002/jgt.21884
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 580.06 kB
Formato Adobe PDF
580.06 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/298494
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact