Characterizing Simultaneous Embedding with Fixed Edges

J. J. Fowler; M. Jünger; S. G. Kobourov; M. Schulz

doi:10.1016/j.endm.2008.06.006

Characterizing Simultaneous Embedding with Fixed Edges

J. J. Fowler, M. Jünger, S. G. Kobourov, M. Schulz

Computer Science

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V of n vertices in the plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same Jordan curve in the simultaneous drawing. We give a necessary condition for when pairs of graphs can have a simultaneous embedding with fixed edges (SEFE). This allows us to determine for which (outer)planar graphs always have a SEFE with all (outer)planar graphs with O (n² lg n) time drawing algorithms. This allows us to decide in O (n) time whether a pair of biconnected outerplanar graphs has a SEFE.

Original language	English (US)
Pages (from-to)	41-44
Number of pages	4
Journal	Electronic Notes in Discrete Mathematics
Volume	31
Issue number	C
DOIs	https://doi.org/10.1016/j.endm.2008.06.006
State	Published - Aug 20 2008

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2008.06.006

Cite this

@article{148cd30d8f584aeaaeec4f1e1b039e54,

title = "Characterizing Simultaneous Embedding with Fixed Edges",

abstract = "A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V of n vertices in the plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same Jordan curve in the simultaneous drawing. We give a necessary condition for when pairs of graphs can have a simultaneous embedding with fixed edges (SEFE). This allows us to determine for which (outer)planar graphs always have a SEFE with all (outer)planar graphs with O (n2 lg n) time drawing algorithms. This allows us to decide in O (n) time whether a pair of biconnected outerplanar graphs has a SEFE.",

author = "Fowler, {J. J.} and M. J{\"u}nger and Kobourov, {S. G.} and M. Schulz",

note = "Funding Information: 1 This work is supported in part by NSF grants CCF-0545743 and ACR-0222920. 2 This work is supported in part by the German Science Foundation (JU204/11-1) and by the German Academic Exchange Service.",

year = "2008",

month = aug,

day = "20",

doi = "10.1016/j.endm.2008.06.006",

language = "English (US)",

volume = "31",

pages = "41--44",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

number = "C",

}

TY - JOUR

T1 - Characterizing Simultaneous Embedding with Fixed Edges

AU - Fowler, J. J.

AU - Jünger, M.

AU - Kobourov, S. G.

AU - Schulz, M.

N1 - Funding Information: 1 This work is supported in part by NSF grants CCF-0545743 and ACR-0222920. 2 This work is supported in part by the German Science Foundation (JU204/11-1) and by the German Academic Exchange Service.

PY - 2008/8/20

Y1 - 2008/8/20

N2 - A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V of n vertices in the plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same Jordan curve in the simultaneous drawing. We give a necessary condition for when pairs of graphs can have a simultaneous embedding with fixed edges (SEFE). This allows us to determine for which (outer)planar graphs always have a SEFE with all (outer)planar graphs with O (n2 lg n) time drawing algorithms. This allows us to decide in O (n) time whether a pair of biconnected outerplanar graphs has a SEFE.

AB - A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V of n vertices in the plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same Jordan curve in the simultaneous drawing. We give a necessary condition for when pairs of graphs can have a simultaneous embedding with fixed edges (SEFE). This allows us to determine for which (outer)planar graphs always have a SEFE with all (outer)planar graphs with O (n2 lg n) time drawing algorithms. This allows us to decide in O (n) time whether a pair of biconnected outerplanar graphs has a SEFE.

UR - http://www.scopus.com/inward/record.url?scp=48549084226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=48549084226&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2008.06.006

DO - 10.1016/j.endm.2008.06.006

M3 - Article

AN - SCOPUS:48549084226

SN - 1571-0653

VL - 31

SP - 41

EP - 44

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - C

ER -

Characterizing Simultaneous Embedding with Fixed Edges

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this