Skip to search boxSkip to navigationSkip to main content

Simultaneous embedding: edge orderings, relative positions, cutvertices

  • T. Bläsius
    ,
  • A. Karrer
    ,
  • I. Rutter
Output:
Contribution to journal
Article
Academic
Peer-review

Information

Output type

Output:
Contribution to journal
Article
Academic
Peer-review

Original language

English

Pages from-to (Number of pages)

Pages 1214-1277 (64 pages)

Journal (Volume, Issue Number)

Algorithmica (Volume 80, Issue 4)

Publication milestones

  • Accepted/In press - 15/03/2017
  • Published - 01/04/2018

Publication status

Published - 01/04/2018

ISSN

0178-4617

Abstract

A simultaneous embedding (with fixed edges) of two graphs G1 and G2 with common graph G=G1∩G2 is a pair of planar drawings of G1 and G2 that coincide on G. It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph G∪=G1∪G2, (2) most separating pairs of G ∪, and (3) connected components of G that are biconnected but not a cycle. Second, we give an O(n 3) -time algorithm solving Sefe for instances with the following restriction. Let u be a pole of a P-node μ in the SPQR-tree of a block of G1 or G2. Then at most three virtual edges of μ may contain common edges incident to u. All algorithms extend to the sunflower case, i.e., to the case of more than two graphs pairwise intersecting in the same common graph.

Metrics

Metrics

Download statistics
Download count
1
Scopus
citations
11
SciVal
FWCI
0.52
SciVal
Author count
3
SciVal
Paper percentile
54
SciVal
citations
11

PlumX, opens in new tab

Citation count
11
Captures
3