TY - JOUR

T1 - Simultaneous graph embedding with bends and circular arcs

AU - Cappos, Justin

AU - Estrella-Balderrama, Alejandro

AU - Fowler, J. Joseph

AU - Kobourov, Stephen G.

N1 - Funding Information:
✩ This work is supported in part by NSF grants CCF-0545743 and ACR-0222920. * Corresponding author. Tel.: +1 (520) 225 7665; fax: +1 (520) 621 4246. E-mail addresses: justin@cs.arizona.edu (J. Cappos), aestrell@cs.arizona.edu (A. Estrella-Balderrama), jfowler@cs.arizona.edu (J.J. Fowler), kobourov@cs.arizona.edu (S.G. Kobourov).

PY - 2009/2

Y1 - 2009/2

N2 - A simultaneous embedding of two vertex-labeled planar graphs on n vertices is possible if there exists a labeled point set of size n such that each of the graphs can be realized on that point set without crossings. We demonstrate how to simultaneously embed a path and an n-level planar graph and how to use radial embeddings for curvilinear simultaneous embeddings of a path and an outerplanar graph. We also show how to use star-shaped levels to find 2-bends per path edge simultaneous embeddings of a path and an outerplanar graph. All embedding algorithms run in O(n) time.

AB - A simultaneous embedding of two vertex-labeled planar graphs on n vertices is possible if there exists a labeled point set of size n such that each of the graphs can be realized on that point set without crossings. We demonstrate how to simultaneously embed a path and an n-level planar graph and how to use radial embeddings for curvilinear simultaneous embeddings of a path and an outerplanar graph. We also show how to use star-shaped levels to find 2-bends per path edge simultaneous embeddings of a path and an outerplanar graph. All embedding algorithms run in O(n) time.

KW - Simultaneous embedding

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

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

U2 - 10.1016/j.comgeo.2008.05.003

DO - 10.1016/j.comgeo.2008.05.003

M3 - Article

AN - SCOPUS:84867931153

SN - 0925-7721

VL - 42

SP - 173

EP - 182

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 2

ER -