Optimal morphs of planar orthogonal drawings II

Arthur van Goethem; Bettina Speckmann; Kevin Verbeek

doi:10.1007/978-3-030-35802-0_3

Optimal morphs of planar orthogonal drawings II

Arthur van Goethem, Bettina Speckmann, Kevin Verbeek

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

2 Downloads (Pure)

Abstract

Van Goethem and Verbeek [12] recently showed how to morph between two planar orthogonal drawings (Forumala Presented). of a connected graph G while preserving planarity, orthogonality, and the complexity of the drawing during the morph. Necessarily drawings (Forumala Presented). must be equivalent, that is, there exists a homeomorphism of the plane that transforms (Forumala Presented). Van Goethem and Verbeek use O(n) linear morphs, where n is the maximum complexity of the input drawings. However, if the graph is disconnected their method requires (Forumala Presented). linear morphs. In this paper we present a refined version of their approach that allows us to also morph between two planar orthogonal drawings of a disconnected graph with O(n) linear morphs while preserving planarity, orthogonality, and linear complexity of the intermediate drawings. Van Goethem and Verbeek measure the structural difference between the two drawings in terms of the so-called spirality (Forumala Presented). and describe a morph from (Forumala Presented). using O(s) linear morphs. We prove that linear morphs are always sufficient to morph between two planar orthogonal drawings, even for disconnected graphs. The resulting morphs are quite natural and visually pleasing.

Original language	English
Title of host publication	Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings
Editors	Daniel Archambault, Csaba D. Tóth
Place of Publication	Cham
Publisher	Springer
Pages	33-45
Number of pages	13
ISBN (Electronic)	978-3-030-35802-0
ISBN (Print)	978-3-030-35801-3
DOIs	https://doi.org/10.1007/978-3-030-35802-0_3
Publication status	Published - 28 Nov 2019
Event	27th International Symposium on Graph Drawing and Network Visualization, GD 2019 - Prague, Czech Republic Duration: 17 Sept 2019 → 20 Sept 2019

Publication series

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

Conference

Conference	27th International Symposium on Graph Drawing and Network Visualization, GD 2019
Country/Territory	Czech Republic
City	Prague
Period	17/09/19 → 20/09/19

Funding

Bettina Speckmann and Kevin Verbeek are supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.023.208 (B.S.) and no. 639.021.541 (K.V.). We want to thank the anonymous reviewers for their extensive feedback.

Access to Document

10.1007/978-3-030-35802-0_3

Cite this

van Goethem, A., Speckmann, B., & Verbeek, K. (2019). Optimal morphs of planar orthogonal drawings II. In D. Archambault, & C. D. Tóth (Eds.), Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings (pp. 33-45). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11904 LNCS). Springer. https://doi.org/10.1007/978-3-030-35802-0_3

van Goethem, Arthur ; Speckmann, Bettina ; Verbeek, Kevin. / Optimal morphs of planar orthogonal drawings II. Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings. editor / Daniel Archambault ; Csaba D. Tóth. Cham : Springer, 2019. pp. 33-45 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2053c5ebba5b42b4ab260cc66f0e0743,

title = "Optimal morphs of planar orthogonal drawings II",

abstract = "Van Goethem and Verbeek [12] recently showed how to morph between two planar orthogonal drawings (Forumala Presented). of a connected graph G while preserving planarity, orthogonality, and the complexity of the drawing during the morph. Necessarily drawings (Forumala Presented). must be equivalent, that is, there exists a homeomorphism of the plane that transforms (Forumala Presented). Van Goethem and Verbeek use O(n) linear morphs, where n is the maximum complexity of the input drawings. However, if the graph is disconnected their method requires (Forumala Presented). linear morphs. In this paper we present a refined version of their approach that allows us to also morph between two planar orthogonal drawings of a disconnected graph with O(n) linear morphs while preserving planarity, orthogonality, and linear complexity of the intermediate drawings. Van Goethem and Verbeek measure the structural difference between the two drawings in terms of the so-called spirality (Forumala Presented). and describe a morph from (Forumala Presented). using O(s) linear morphs. We prove that linear morphs are always sufficient to morph between two planar orthogonal drawings, even for disconnected graphs. The resulting morphs are quite natural and visually pleasing.",

author = "{van Goethem}, Arthur and Bettina Speckmann and Kevin Verbeek",

year = "2019",

month = nov,

day = "28",

doi = "10.1007/978-3-030-35802-0_3",

language = "English",

isbn = "978-3-030-35801-3",

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

publisher = "Springer",

pages = "33--45",

editor = "Daniel Archambault and T{\'o}th, {Csaba D.}",

booktitle = "Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings",

address = "Germany",

note = "27th International Symposium on Graph Drawing and Network Visualization, GD 2019 ; Conference date: 17-09-2019 Through 20-09-2019",

}

van Goethem, A, Speckmann, B & Verbeek, K 2019, Optimal morphs of planar orthogonal drawings II. in D Archambault & CD Tóth (eds), Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11904 LNCS, Springer, Cham, pp. 33-45, 27th International Symposium on Graph Drawing and Network Visualization, GD 2019, Prague, Czech Republic, 17/09/19. https://doi.org/10.1007/978-3-030-35802-0_3

Optimal morphs of planar orthogonal drawings II. / van Goethem, Arthur; Speckmann, Bettina ; Verbeek, Kevin.
Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings. ed. / Daniel Archambault; Csaba D. Tóth. Cham: Springer, 2019. p. 33-45 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11904 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Optimal morphs of planar orthogonal drawings II

AU - van Goethem, Arthur

AU - Speckmann, Bettina

AU - Verbeek, Kevin

PY - 2019/11/28

Y1 - 2019/11/28

N2 - Van Goethem and Verbeek [12] recently showed how to morph between two planar orthogonal drawings (Forumala Presented). of a connected graph G while preserving planarity, orthogonality, and the complexity of the drawing during the morph. Necessarily drawings (Forumala Presented). must be equivalent, that is, there exists a homeomorphism of the plane that transforms (Forumala Presented). Van Goethem and Verbeek use O(n) linear morphs, where n is the maximum complexity of the input drawings. However, if the graph is disconnected their method requires (Forumala Presented). linear morphs. In this paper we present a refined version of their approach that allows us to also morph between two planar orthogonal drawings of a disconnected graph with O(n) linear morphs while preserving planarity, orthogonality, and linear complexity of the intermediate drawings. Van Goethem and Verbeek measure the structural difference between the two drawings in terms of the so-called spirality (Forumala Presented). and describe a morph from (Forumala Presented). using O(s) linear morphs. We prove that linear morphs are always sufficient to morph between two planar orthogonal drawings, even for disconnected graphs. The resulting morphs are quite natural and visually pleasing.

AB - Van Goethem and Verbeek [12] recently showed how to morph between two planar orthogonal drawings (Forumala Presented). of a connected graph G while preserving planarity, orthogonality, and the complexity of the drawing during the morph. Necessarily drawings (Forumala Presented). must be equivalent, that is, there exists a homeomorphism of the plane that transforms (Forumala Presented). Van Goethem and Verbeek use O(n) linear morphs, where n is the maximum complexity of the input drawings. However, if the graph is disconnected their method requires (Forumala Presented). linear morphs. In this paper we present a refined version of their approach that allows us to also morph between two planar orthogonal drawings of a disconnected graph with O(n) linear morphs while preserving planarity, orthogonality, and linear complexity of the intermediate drawings. Van Goethem and Verbeek measure the structural difference between the two drawings in terms of the so-called spirality (Forumala Presented). and describe a morph from (Forumala Presented). using O(s) linear morphs. We prove that linear morphs are always sufficient to morph between two planar orthogonal drawings, even for disconnected graphs. The resulting morphs are quite natural and visually pleasing.

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

U2 - 10.1007/978-3-030-35802-0_3

DO - 10.1007/978-3-030-35802-0_3

M3 - Conference contribution

AN - SCOPUS:85076896754

SN - 978-3-030-35801-3

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

SP - 33

EP - 45

BT - Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings

A2 - Archambault, Daniel

A2 - Tóth, Csaba D.

PB - Springer

CY - Cham

T2 - 27th International Symposium on Graph Drawing and Network Visualization, GD 2019

Y2 - 17 September 2019 through 20 September 2019

ER -

van Goethem A, Speckmann B , Verbeek K. Optimal morphs of planar orthogonal drawings II. In Archambault D, Tóth CD, editors, Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings. Cham: Springer. 2019. p. 33-45. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-35802-0_3

Optimal morphs of planar orthogonal drawings II

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this