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].
Titolo: | SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs | |
Autori: | ||
Data di pubblicazione: | 2016 | |
Rivista: | ||
Citazione: | 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]. | |
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. | |
Handle: | http://hdl.handle.net/11590/298494 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |