Identifying Cluttering Edges in Near-Planar Graphs

Loading...
Thumbnail Image
Date
2023
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
Planar drawings of graphs tend to be favored over non-planar drawings. Testing planarity and creating a planar layout of a planar graph can be done in linear time. However, creating readable drawings of nearly planar graphs remains a challenge. We therefore seek to answer which edges of nearly planar graphs create clutter in their drawings generated by mainstream graph drawing algorithms. We present a heuristic to identify problematic edges in nearly planar graphs and adjust their weights in order to produce higher quality layouts with spring-based drawing algorithms. Our experiments show that our heuristic produces significantly higher quality drawings for augmented grid graphs, augmented triangulations, and deep triangulations.
Description

CCS Concepts: Human-centered computing -> Graph drawings

        
@inproceedings{
10.2312:evs.20231048
, booktitle = {
EuroVis 2023 - Short Papers
}, editor = {
Hoellt, Thomas
and
Aigner, Wolfgang
and
Wang, Bei
}, title = {{
Identifying Cluttering Edges in Near-Planar Graphs
}}, author = {
Wageningen, Simon van
and
Mchedlidze, Tamara
and
Telea, Alexandru
}, year = {
2023
}, publisher = {
The Eurographics Association
}, ISBN = {
978-3-03868-219-6
}, DOI = {
10.2312/evs.20231048
} }
Citation
Collections