No Cover Image

Journal article 293 views 23 downloads

Faster Edge‐Path Bundling through Graph Spanners

Markus Wallinger, Daniel Archambault Orcid Logo, David Auber, Martin Nöllenburg, Jaakko Peltonen

Computer Graphics Forum

Swansea University Author: Daniel Archambault Orcid Logo

  • 62893.pdf

    PDF | Version of Record

    © 2023 The Authors.Computer Graphics Forum published by Eurographics - The European Association for Computer Graphics and John Wiley & Sons Ltd.This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium,provided the original work is properly cited.

    Download (1.8MB)

Check full text

DOI (Published version): 10.1111/cgf.14789

Abstract

Edge-Path bundling is a recent edge bundling approach that does not incur ambiguities caused by bundling disconnected edges together. Although the approach produces less ambiguous bundlings, it suffers from high computational cost. In this paper, we present a new Edge-Path bundling approach that inc...

Full description

Published in: Computer Graphics Forum
ISSN: 0167-7055 1467-8659
Published: Wiley
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa62893
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2023-03-09T10:30:52Z
last_indexed 2023-04-19T03:23:48Z
id cronfa62893
recordtype SURis
fullrecord <?xml version="1.0" encoding="utf-8"?><rfc1807 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"><bib-version>v2</bib-version><id>62893</id><entry>2023-03-09</entry><title>Faster Edge‐Path Bundling through Graph Spanners</title><swanseaauthors><author><sid>8fa6987716a22304ef04d3c3d50ef266</sid><ORCID>0000-0003-4978-8479</ORCID><firstname>Daniel</firstname><surname>Archambault</surname><name>Daniel Archambault</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2023-03-09</date><deptcode>SCS</deptcode><abstract>Edge-Path bundling is a recent edge bundling approach that does not incur ambiguities caused by bundling disconnected edges together. Although the approach produces less ambiguous bundlings, it suffers from high computational cost. In this paper, we present a new Edge-Path bundling approach that increases the computational speed of the algorithm without reducing the quality of the bundling. First, we demonstrate that biconnected components can be processed separately in an Edge-Path bundling of a graph without changing the result. Then, we present a new edge bundling algorithm that is based on observing and exploiting a strong relationship between Edge-Path bundling and graph spanners. Although the worst case complexity of the approach is the same as of the original Edge-Path bundling algorithm, we conduct experiments to demonstrate that the new approach is 5–256 times faster than Edge-Path bundling depending on the dataset, which brings its practical running time more in line with traditional edge bundling algorithms.</abstract><type>Journal Article</type><journal>Computer Graphics Forum</journal><volume/><journalNumber/><paginationStart/><paginationEnd/><publisher>Wiley</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>0167-7055</issnPrint><issnElectronic>1467-8659</issnElectronic><keywords>Computational geometry, information visualization, visualization</keywords><publishedDay>0</publishedDay><publishedMonth>0</publishedMonth><publishedYear>0</publishedYear><publishedDate>0001-01-01</publishedDate><doi>10.1111/cgf.14789</doi><url>http://dx.doi.org/10.1111/cgf.14789</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm>Another institution paid the OA fee</apcterm><funders/><projectreference/><lastEdited>2023-05-22T15:22:33.0205259</lastEdited><Created>2023-03-09T10:16:07.7297612</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Markus</firstname><surname>Wallinger</surname><order>1</order></author><author><firstname>Daniel</firstname><surname>Archambault</surname><orcid>0000-0003-4978-8479</orcid><order>2</order></author><author><firstname>David</firstname><surname>Auber</surname><order>3</order></author><author><firstname>Martin</firstname><surname>Nöllenburg</surname><order>4</order></author><author><firstname>Jaakko</firstname><surname>Peltonen</surname><order>5</order></author></authors><documents><document><filename>62893__27053__8a3d0816eb264750af5d724583f066c2.pdf</filename><originalFilename>62893.pdf</originalFilename><uploaded>2023-04-14T15:46:56.3224234</uploaded><type>Output</type><contentLength>1892160</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>© 2023 The Authors.Computer Graphics Forum published by Eurographics - The European Association for Computer Graphics and John Wiley &amp; Sons Ltd.This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium,provided the original work is properly cited.</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>http://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling v2 62893 2023-03-09 Faster Edge‐Path Bundling through Graph Spanners 8fa6987716a22304ef04d3c3d50ef266 0000-0003-4978-8479 Daniel Archambault Daniel Archambault true false 2023-03-09 SCS Edge-Path bundling is a recent edge bundling approach that does not incur ambiguities caused by bundling disconnected edges together. Although the approach produces less ambiguous bundlings, it suffers from high computational cost. In this paper, we present a new Edge-Path bundling approach that increases the computational speed of the algorithm without reducing the quality of the bundling. First, we demonstrate that biconnected components can be processed separately in an Edge-Path bundling of a graph without changing the result. Then, we present a new edge bundling algorithm that is based on observing and exploiting a strong relationship between Edge-Path bundling and graph spanners. Although the worst case complexity of the approach is the same as of the original Edge-Path bundling algorithm, we conduct experiments to demonstrate that the new approach is 5–256 times faster than Edge-Path bundling depending on the dataset, which brings its practical running time more in line with traditional edge bundling algorithms. Journal Article Computer Graphics Forum Wiley 0167-7055 1467-8659 Computational geometry, information visualization, visualization 0 0 0 0001-01-01 10.1111/cgf.14789 http://dx.doi.org/10.1111/cgf.14789 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University Another institution paid the OA fee 2023-05-22T15:22:33.0205259 2023-03-09T10:16:07.7297612 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Markus Wallinger 1 Daniel Archambault 0000-0003-4978-8479 2 David Auber 3 Martin Nöllenburg 4 Jaakko Peltonen 5 62893__27053__8a3d0816eb264750af5d724583f066c2.pdf 62893.pdf 2023-04-14T15:46:56.3224234 Output 1892160 application/pdf Version of Record true © 2023 The Authors.Computer Graphics Forum published by Eurographics - The European Association for Computer Graphics and John Wiley & Sons Ltd.This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium,provided the original work is properly cited. true eng http://creativecommons.org/licenses/by/4.0/
title Faster Edge‐Path Bundling through Graph Spanners
spellingShingle Faster Edge‐Path Bundling through Graph Spanners
Daniel Archambault
title_short Faster Edge‐Path Bundling through Graph Spanners
title_full Faster Edge‐Path Bundling through Graph Spanners
title_fullStr Faster Edge‐Path Bundling through Graph Spanners
title_full_unstemmed Faster Edge‐Path Bundling through Graph Spanners
title_sort Faster Edge‐Path Bundling through Graph Spanners
author_id_str_mv 8fa6987716a22304ef04d3c3d50ef266
author_id_fullname_str_mv 8fa6987716a22304ef04d3c3d50ef266_***_Daniel Archambault
author Daniel Archambault
author2 Markus Wallinger
Daniel Archambault
David Auber
Martin Nöllenburg
Jaakko Peltonen
format Journal article
container_title Computer Graphics Forum
institution Swansea University
issn 0167-7055
1467-8659
doi_str_mv 10.1111/cgf.14789
publisher Wiley
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url http://dx.doi.org/10.1111/cgf.14789
document_store_str 1
active_str 0
description Edge-Path bundling is a recent edge bundling approach that does not incur ambiguities caused by bundling disconnected edges together. Although the approach produces less ambiguous bundlings, it suffers from high computational cost. In this paper, we present a new Edge-Path bundling approach that increases the computational speed of the algorithm without reducing the quality of the bundling. First, we demonstrate that biconnected components can be processed separately in an Edge-Path bundling of a graph without changing the result. Then, we present a new edge bundling algorithm that is based on observing and exploiting a strong relationship between Edge-Path bundling and graph spanners. Although the worst case complexity of the approach is the same as of the original Edge-Path bundling algorithm, we conduct experiments to demonstrate that the new approach is 5–256 times faster than Edge-Path bundling depending on the dataset, which brings its practical running time more in line with traditional edge bundling algorithms.
published_date 0001-01-01T15:22:31Z
_version_ 1766604513004748800
score 10.998048

Similar Items