Loading…
Upward Planar Morphs
We prove that, given two topologically-equivalent upward planar straight-line drawings of an n -vertex directed graph G , there always exists a morph between them such that all the intermediate drawings of the morph are upward planar and straight-line. Such a morph consists of O (1) morphing steps i...
Saved in:
| Published in: | Algorithmica 2020-10, Vol.82 (10), p.2985-3017 |
|---|---|
| Main Authors: | , , , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c319t-b75a1d89dde588acef97d27fae5b14f11f8cc5f2933dbf00abf10458501feb0e3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c319t-b75a1d89dde588acef97d27fae5b14f11f8cc5f2933dbf00abf10458501feb0e3 |
| container_end_page | 3017 |
| container_issue | 10 |
| container_start_page | 2985 |
| container_title | Algorithmica |
| container_volume | 82 |
| creator | Da Lozzo, Giordano Di Battista, Giuseppe Frati, Fabrizio Patrignani, Maurizio Roselli, Vincenzo |
| description | We prove that, given two topologically-equivalent upward planar straight-line drawings of an
n
-vertex directed graph
G
, there always exists a morph between them such that all the intermediate drawings of the morph are upward planar and straight-line. Such a morph consists of
O
(1) morphing steps if
G
is a reduced planar
st
-graph,
O
(
n
) morphing steps if
G
is a planar
st
-graph,
O
(
n
) morphing steps if
G
is a reduced upward planar graph, and
O
(
n
2
)
morphing steps if
G
is a general upward planar graph. Further, we show that
Ω
(
n
)
morphing steps might be necessary for an upward planar morph between two topologically-equivalent upward planar straight-line drawings of an
n
-vertex path. |
| doi_str_mv | 10.1007/s00453-020-00714-6 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2450270600</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2450270600</sourcerecordid><originalsourceid>FETCH-LOGICAL-c319t-b75a1d89dde588acef97d27fae5b14f11f8cc5f2933dbf00abf10458501feb0e3</originalsourceid><addsrcrecordid>eNp9j01LAzEQhoMouFZvnjwVPMfO5GOTPUrRKlT0YM8h2SRqqbtr0iL-e6MreOtpGHifd-Yh5ALhCgHULAMIySkwoGVFQesDUqHgjIIUeEgqQKWpqFEdk5Oc1wDIVFNX5Hw1fNrkp08b29k0fejT8JpPyVG0mxzO_uaErG5vnud3dPm4uJ9fL2nLsdlSp6RFrxvvg9TatiE2yjMVbZAORUSMum1lZA3n3kUA6yKWN7UEjMFB4BNyOfYOqf_Yhbw1636XunLSMCGBKagBSoqNqTb1OacQzZDe3m36Mgjmx96M9qbYm197UxeIj1Au4e4lpP_qPdQ3XrxbIA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2450270600</pqid></control><display><type>article</type><title>Upward Planar Morphs</title><source>Springer Nature</source><creator>Da Lozzo, Giordano ; Di Battista, Giuseppe ; Frati, Fabrizio ; Patrignani, Maurizio ; Roselli, Vincenzo</creator><creatorcontrib>Da Lozzo, Giordano ; Di Battista, Giuseppe ; Frati, Fabrizio ; Patrignani, Maurizio ; Roselli, Vincenzo</creatorcontrib><description>We prove that, given two topologically-equivalent upward planar straight-line drawings of an
n
-vertex directed graph
G
, there always exists a morph between them such that all the intermediate drawings of the morph are upward planar and straight-line. Such a morph consists of
O
(1) morphing steps if
G
is a reduced planar
st
-graph,
O
(
n
) morphing steps if
G
is a planar
st
-graph,
O
(
n
) morphing steps if
G
is a reduced upward planar graph, and
O
(
n
2
)
morphing steps if
G
is a general upward planar graph. Further, we show that
Ω
(
n
)
morphing steps might be necessary for an upward planar morph between two topologically-equivalent upward planar straight-line drawings of an
n
-vertex path.</description><identifier>ISSN: 0178-4617</identifier><identifier>EISSN: 1432-0541</identifier><identifier>DOI: 10.1007/s00453-020-00714-6</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Algorithm Analysis and Problem Complexity ; Algorithms ; Computer Science ; Computer Systems Organization and Communication Networks ; Data Structures and Information Theory ; Equivalence ; Graph theory ; Mathematics of Computing ; Morphing ; Theory of Computation</subject><ispartof>Algorithmica, 2020-10, Vol.82 (10), p.2985-3017</ispartof><rights>Springer Science+Business Media, LLC, part of Springer Nature 2020</rights><rights>Springer Science+Business Media, LLC, part of Springer Nature 2020.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c319t-b75a1d89dde588acef97d27fae5b14f11f8cc5f2933dbf00abf10458501feb0e3</citedby><cites>FETCH-LOGICAL-c319t-b75a1d89dde588acef97d27fae5b14f11f8cc5f2933dbf00abf10458501feb0e3</cites><orcidid>0000-0001-5987-8713</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27915,27916</link.rule.ids></links><search><creatorcontrib>Da Lozzo, Giordano</creatorcontrib><creatorcontrib>Di Battista, Giuseppe</creatorcontrib><creatorcontrib>Frati, Fabrizio</creatorcontrib><creatorcontrib>Patrignani, Maurizio</creatorcontrib><creatorcontrib>Roselli, Vincenzo</creatorcontrib><title>Upward Planar Morphs</title><title>Algorithmica</title><addtitle>Algorithmica</addtitle><description>We prove that, given two topologically-equivalent upward planar straight-line drawings of an
n
-vertex directed graph
G
, there always exists a morph between them such that all the intermediate drawings of the morph are upward planar and straight-line. Such a morph consists of
O
(1) morphing steps if
G
is a reduced planar
st
-graph,
O
(
n
) morphing steps if
G
is a planar
st
-graph,
O
(
n
) morphing steps if
G
is a reduced upward planar graph, and
O
(
n
2
)
morphing steps if
G
is a general upward planar graph. Further, we show that
Ω
(
n
)
morphing steps might be necessary for an upward planar morph between two topologically-equivalent upward planar straight-line drawings of an
n
-vertex path.</description><subject>Algorithm Analysis and Problem Complexity</subject><subject>Algorithms</subject><subject>Computer Science</subject><subject>Computer Systems Organization and Communication Networks</subject><subject>Data Structures and Information Theory</subject><subject>Equivalence</subject><subject>Graph theory</subject><subject>Mathematics of Computing</subject><subject>Morphing</subject><subject>Theory of Computation</subject><issn>0178-4617</issn><issn>1432-0541</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><recordid>eNp9j01LAzEQhoMouFZvnjwVPMfO5GOTPUrRKlT0YM8h2SRqqbtr0iL-e6MreOtpGHifd-Yh5ALhCgHULAMIySkwoGVFQesDUqHgjIIUeEgqQKWpqFEdk5Oc1wDIVFNX5Hw1fNrkp08b29k0fejT8JpPyVG0mxzO_uaErG5vnud3dPm4uJ9fL2nLsdlSp6RFrxvvg9TatiE2yjMVbZAORUSMum1lZA3n3kUA6yKWN7UEjMFB4BNyOfYOqf_Yhbw1636XunLSMCGBKagBSoqNqTb1OacQzZDe3m36Mgjmx96M9qbYm197UxeIj1Au4e4lpP_qPdQ3XrxbIA</recordid><startdate>20201001</startdate><enddate>20201001</enddate><creator>Da Lozzo, Giordano</creator><creator>Di Battista, Giuseppe</creator><creator>Frati, Fabrizio</creator><creator>Patrignani, Maurizio</creator><creator>Roselli, Vincenzo</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><orcidid>https://orcid.org/0000-0001-5987-8713</orcidid></search><sort><creationdate>20201001</creationdate><title>Upward Planar Morphs</title><author>Da Lozzo, Giordano ; Di Battista, Giuseppe ; Frati, Fabrizio ; Patrignani, Maurizio ; Roselli, Vincenzo</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c319t-b75a1d89dde588acef97d27fae5b14f11f8cc5f2933dbf00abf10458501feb0e3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Algorithm Analysis and Problem Complexity</topic><topic>Algorithms</topic><topic>Computer Science</topic><topic>Computer Systems Organization and Communication Networks</topic><topic>Data Structures and Information Theory</topic><topic>Equivalence</topic><topic>Graph theory</topic><topic>Mathematics of Computing</topic><topic>Morphing</topic><topic>Theory of Computation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Da Lozzo, Giordano</creatorcontrib><creatorcontrib>Di Battista, Giuseppe</creatorcontrib><creatorcontrib>Frati, Fabrizio</creatorcontrib><creatorcontrib>Patrignani, Maurizio</creatorcontrib><creatorcontrib>Roselli, Vincenzo</creatorcontrib><collection>CrossRef</collection><jtitle>Algorithmica</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Da Lozzo, Giordano</au><au>Di Battista, Giuseppe</au><au>Frati, Fabrizio</au><au>Patrignani, Maurizio</au><au>Roselli, Vincenzo</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Upward Planar Morphs</atitle><jtitle>Algorithmica</jtitle><stitle>Algorithmica</stitle><date>2020-10-01</date><risdate>2020</risdate><volume>82</volume><issue>10</issue><spage>2985</spage><epage>3017</epage><pages>2985-3017</pages><issn>0178-4617</issn><eissn>1432-0541</eissn><abstract>We prove that, given two topologically-equivalent upward planar straight-line drawings of an
n
-vertex directed graph
G
, there always exists a morph between them such that all the intermediate drawings of the morph are upward planar and straight-line. Such a morph consists of
O
(1) morphing steps if
G
is a reduced planar
st
-graph,
O
(
n
) morphing steps if
G
is a planar
st
-graph,
O
(
n
) morphing steps if
G
is a reduced upward planar graph, and
O
(
n
2
)
morphing steps if
G
is a general upward planar graph. Further, we show that
Ω
(
n
)
morphing steps might be necessary for an upward planar morph between two topologically-equivalent upward planar straight-line drawings of an
n
-vertex path.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s00453-020-00714-6</doi><tpages>33</tpages><orcidid>https://orcid.org/0000-0001-5987-8713</orcidid></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0178-4617 |
| ispartof | Algorithmica, 2020-10, Vol.82 (10), p.2985-3017 |
| issn | 0178-4617 1432-0541 |
| language | eng |
| recordid | cdi_proquest_journals_2450270600 |
| source | Springer Nature |
| subjects | Algorithm Analysis and Problem Complexity Algorithms Computer Science Computer Systems Organization and Communication Networks Data Structures and Information Theory Equivalence Graph theory Mathematics of Computing Morphing Theory of Computation |
| title | Upward Planar Morphs |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-14T21%3A54%3A02IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Upward%20Planar%20Morphs&rft.jtitle=Algorithmica&rft.au=Da%20Lozzo,%20Giordano&rft.date=2020-10-01&rft.volume=82&rft.issue=10&rft.spage=2985&rft.epage=3017&rft.pages=2985-3017&rft.issn=0178-4617&rft.eissn=1432-0541&rft_id=info:doi/10.1007/s00453-020-00714-6&rft_dat=%3Cproquest_cross%3E2450270600%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c319t-b75a1d89dde588acef97d27fae5b14f11f8cc5f2933dbf00abf10458501feb0e3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2450270600&rft_id=info:pmid/&rfr_iscdi=true |