Simultaneous graph embedding with bends and circular arcs

Justin Cappos; Alejandro Estrella-Balderrama; J. Joseph Fowler; Stephen G. Kobourov

doi:10.1016/j.comgeo.2008.05.003

Simultaneous graph embedding with bends and circular arcs

Justin Cappos, Alejandro Estrella-Balderrama, J. Joseph Fowler, Stephen G. Kobourov

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

Abstract

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.

Original language	English (US)
Pages (from-to)	173-182
Number of pages	10
Journal	Computational Geometry: Theory and Applications
Volume	42
Issue number	2
DOIs	https://doi.org/10.1016/j.comgeo.2008.05.003
State	Published - Feb 2009

Keywords

Simultaneous embedding

ASJC Scopus subject areas

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/j.comgeo.2008.05.003

Cite this

@article{ea750b9fd7074d2d882e52a3de4044b7,

title = "Simultaneous graph embedding with bends and circular arcs",

abstract = "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.",

keywords = "Simultaneous embedding",

author = "Justin Cappos and Alejandro Estrella-Balderrama and Fowler, {J. Joseph} and Kobourov, {Stephen G.}",

note = "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: [email protected] (J. Cappos), [email protected] (A. Estrella-Balderrama), [email protected] (J.J. Fowler), [email protected] (S.G. Kobourov).",

year = "2009",

month = feb,

doi = "10.1016/j.comgeo.2008.05.003",

language = "English (US)",

volume = "42",

pages = "173--182",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "2",

}

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: [email protected] (J. Cappos), [email protected] (A. Estrella-Balderrama), [email protected] (J.J. Fowler), [email protected] (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 -

Simultaneous graph embedding with bends and circular arcs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this