Fowler, J. Joseph, Juenger, Michael, Kobourov, Stephen G. and Schulz, Michael (2011). Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges. Comput. Geom.-Theory Appl., 44 (8). S. 385 - 399. AMSTERDAM: ELSEVIER SCIENCE BV. ISSN 0925-7721
Full text not available from this repository.Abstract
A set of planar graphs {G(1) (V, E-1), ..., G(k)(V, E-k)} admits a simultaneous embedding if they can be drawn on the same pointset P of order n in the Euclidean plane such that each point in P corresponds one-to-one to a vertex in V and each edge in E-i does not cross any other edge in E-i (except at endpoints) for i is an element of {1, ..., k}. A fixed edge is an edge (u, v) that is drawn using the same simple curve for each graph G(i) whose edge set E-i contains the edge (u, v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to K-5 or K-3,K-3 to admit a simultaneous embedding with fixed edges (SEFE). This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide O(n(4))-time algorithms to compute a SEFE. (C) 2011 Elsevier B.V. All rights reserved.
Item Type: | Journal Article | ||||||||||||||||||||
Creators: |
|
||||||||||||||||||||
URN: | urn:nbn:de:hbz:38-488759 | ||||||||||||||||||||
DOI: | 10.1016/j.comgeo.2011.02.002 | ||||||||||||||||||||
Journal or Publication Title: | Comput. Geom.-Theory Appl. | ||||||||||||||||||||
Volume: | 44 | ||||||||||||||||||||
Number: | 8 | ||||||||||||||||||||
Page Range: | S. 385 - 399 | ||||||||||||||||||||
Date: | 2011 | ||||||||||||||||||||
Publisher: | ELSEVIER SCIENCE BV | ||||||||||||||||||||
Place of Publication: | AMSTERDAM | ||||||||||||||||||||
ISSN: | 0925-7721 | ||||||||||||||||||||
Language: | English | ||||||||||||||||||||
Faculty: | Unspecified | ||||||||||||||||||||
Divisions: | Unspecified | ||||||||||||||||||||
Subjects: | no entry | ||||||||||||||||||||
Uncontrolled Keywords: |
|
||||||||||||||||||||
URI: | http://kups.ub.uni-koeln.de/id/eprint/48875 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
View Item |