2012/04/13 by Thomas Bläsius, Ignaz Rutter, Bläsius, Thomas +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2 #cs.DM #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1204.2903
34 pages, 8 figures
openalex publication_date 2012/04/13 · arxiv created 2015/06/19 · arxiv updated 2015/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem Simultaneous Embedding with Fixed Edges (SEFE) asks for two planar graph G1 = (V1, E1) and G2 = (V2, E2) sharing a common subgraph G = G1 ∩ G2 whether they admit planar drawings such that the common graph is drawn the same in both. Previous results on this problem require G, G1 and G2 to be connected. This paper is a first step towards solving instances where these graphs are disconnected. First, we show that an instance of the general SEFE-problem can be reduced in linear time to an equivalent instance where V1 = V2 and G1 and G2 are connected. This shows that it can be assumed without loss of generality that both input graphs are connected. Second, we consider instances where G is disconnected. We show that SEFE can be solved in linear time if G is a family of disjoint cycles by introducing the CC-tree, which represents all simultaneous embeddings. We extend these results (including the CC-tree) to the case where G consists of arbitrary connected components, each with a fixed embedding. Note that previous results require G to be connected and thus do not need to care about relative positions of connected components. By contrast, we assume the embedding of each connected component to be fixed and thus focus on these relative positions. As SEFE requires to deal with both, embeddings of connected components and their relative positions, this complements previous work.