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