SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs

2013/09/18 by Patrizio Angelini, Angelini, Patrizio, William Evans +5
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1309.4713

openalex publication_date 2013/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that every n-vertex planar graph admits a simultaneous embedding with no mapping and with fixed edges with any (n/2)-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 n/2 vertices. Also, we show that every n-vertex planar graph and every n-vertex planar partial 3-tree admit a simultaneous embedding with no mapping and with fixed edges.

Related

• On Simultaneous Graph Embedding
• Simultaneous Embeddings with Few Bends and Crossings
• A logarithmic bound for simultaneous embeddings of planar graphs
• A pair of trees without a simultaneous geometric embedding in the plane
• A simple and elementary proof of Whitney's unique embedding theorem