Simplified emanation graphs: a sparse plane spanner with Steiner points

DOI10.1007/978-3-030-38919-2_50MaRDI QIDQ3297791zbMATH OpenOpenAlexFDO

Authors Bardia Hamedmohseni, Zahed Rahmati, Debajyoti Mondal

Publication date 20 July 2020

Published in SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.10376

zbMATH Keywords

mesh generationnetwork visualizationplane spanners

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: An emanation graph of grade $k$ on a set of points is a plane spanner made by shooting $2^{k+1}$ equally spaced rays from each point, where the shorter rays stop the longer ones upon collision. The collision points are the Steiner points of the spanner. Emanation graphs of grade one were studied by Mondal and Nachmanson in the context of network visualization. They proved that the spanning ratio of such a graph is bounded by $(2+sqrt2)approx3.414$. We improve this upper bound to $sqrt10approx3.162$ and show this to be tight, i.e., there exist emanation graphs with spanning ratio $sqrt10$. We show that for every fixed $k$, the emanation graphs of grade $k$ are constant spanners, where the constant factor depends on $k$. An emanation graph of grade two may have twice the number of edges compared to grade one graphs. Hence we introduce a heuristic method for simplifying them. In particular, we compare simplified emanation graphs against Shewchuk's constrained Delaunay triangulations on both synthetic and real-life datasets. Our experimental results reveal that the simplified emanation graphs outperform constrained Delaunay triangulations in common quality measures (e.g., edge count, angular resolution, average degree, total edge length) while maintaining a comparable spanning ratio and Steiner point count.

Recommendations

• Emanation graph: a plane geometric spanner with Steiner points
• On geometric spanners of Euclidean and unit disk graphs
• On Spanners of Geometric Graphs
• Improved local algorithms for spanner construction

Cites work

• Graph Drawing
• GraphMaps: browsing large graphs as interactive maps
• On plane geometric spanners: a survey and open problems

Cited in

(1)

• Emanation graph: a plane geometric spanner with Steiner points

Describes a project that uses

Uses Software

• Triangle
• NetworkX
• SciPy
• GitHub

This page was built for publication: Simplified emanation graphs: a sparse plane spanner with Steiner points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297791)