Simultaneous graph embedding with bends and circular arcs

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

doi:10.1007/978-3-540-70904-6_11

Simultaneous graph embedding with bends and circular arcs

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider the problem of simultaneous embedding of planar graphs. 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)
Title of host publication	Graph Drawing - 14th International Symposium, GD 2006, Revised Papers
Publisher	Springer Verlag
Pages	95-107
Number of pages	13
ISBN (Print)	9783540709039
DOIs	https://doi.org/10.1007/978-3-540-70904-6_11
State	Published - 2007
Event	14th International Symposium on Graph Drawing, GD 2006 - Karlsruhe, Germany Duration: Sep 18 2006 → Sep 19 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4372 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	14th International Symposium on Graph Drawing, GD 2006
Country/Territory	Germany
City	Karlsruhe
Period	9/18/06 → 9/19/06

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-70904-6_11

Cite this

Cappos, J., Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2007). Simultaneous graph embedding with bends and circular arcs. In Graph Drawing - 14th International Symposium, GD 2006, Revised Papers (pp. 95-107). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4372 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-70904-6_11

Simultaneous graph embedding with bends and circular arcs. / Cappos, Justin; Estrella-Balderrama, Alejandro; Fowler, J. Joseph et al.
Graph Drawing - 14th International Symposium, GD 2006, Revised Papers. Springer Verlag, 2007. p. 95-107 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4372 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cappos, J, Estrella-Balderrama, A, Fowler, JJ & Kobourov, SG 2007, Simultaneous graph embedding with bends and circular arcs. in Graph Drawing - 14th International Symposium, GD 2006, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4372 LNCS, Springer Verlag, pp. 95-107, 14th International Symposium on Graph Drawing, GD 2006, Karlsruhe, Germany, 9/18/06. https://doi.org/10.1007/978-3-540-70904-6_11

Cappos J, Estrella-Balderrama A, Fowler JJ, Kobourov SG. Simultaneous graph embedding with bends and circular arcs. In Graph Drawing - 14th International Symposium, GD 2006, Revised Papers. Springer Verlag. 2007. p. 95-107. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-70904-6_11

Cappos, Justin ; Estrella-Balderrama, Alejandro ; Fowler, J. Joseph et al. / Simultaneous graph embedding with bends and circular arcs. Graph Drawing - 14th International Symposium, GD 2006, Revised Papers. Springer Verlag, 2007. pp. 95-107 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e1ca62d5701a45e6a56f73c58457724a,

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

abstract = "We consider the problem of simultaneous embedding of planar graphs. 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.",

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).; 14th International Symposium on Graph Drawing, GD 2006 ; Conference date: 18-09-2006 Through 19-09-2006",

year = "2007",

doi = "10.1007/978-3-540-70904-6_11",

language = "English (US)",

isbn = "9783540709039",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "95--107",

booktitle = "Graph Drawing - 14th International Symposium, GD 2006, Revised Papers",

}

TY - GEN

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 - 2007

Y1 - 2007

N2 - We consider the problem of simultaneous embedding of planar graphs. 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 - We consider the problem of simultaneous embedding of planar graphs. 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.

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

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

U2 - 10.1007/978-3-540-70904-6_11

DO - 10.1007/978-3-540-70904-6_11

M3 - Conference contribution

AN - SCOPUS:38149123497

SN - 9783540709039

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 95

EP - 107

BT - Graph Drawing - 14th International Symposium, GD 2006, Revised Papers

PB - Springer Verlag

T2 - 14th International Symposium on Graph Drawing, GD 2006

Y2 - 18 September 2006 through 19 September 2006

ER -

Simultaneous graph embedding with bends and circular arcs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this