Identifying Cluttering Edges in Near-Planar Graphs

Autor:	van Wageningen, Simon, Mchedlidze, Tamara, Telea, Alexandru
Rok vydání:	2023
Předmět:	Computer Science - Computational Geometry Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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. Comment: Short paper for proceedings of EuroVis 2023 conference
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2304.07274 Zobrazit plný text záznamu View this record from Arxiv