There are Plane Spanners of Maximum Degree 4

DOI10.1145/2582112.2582141MaRDI QIDQ4635524zbMATH OpenOpenAlexFDO

Authors Nicolas Bonichon, Ljubomir Perković, Ge Xia, Iyad Kanj

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2582112.2582141

zbMATH Keywords

bounded degreeDelaunay triangulationgeometric graphplane spannerstretch factor

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Towards plane spanners of degree 3
• Towards plane spanners of degree 3
• Euclidean spanner graphs with degree four
• On bounded degree plane strong geometric spanners
• Constructing plane spanners of bounded degree and low weight
• scientific article; zbMATH DE number 1947396
• On spanning subgraphs of 4-connected planar graphs
• The spanning maximal planar subgraph problem for some classes of complete 4-partite graphs

Cited in

(9)

• Euclidean spanner graphs with degree four
• There are plane spanners of degree 4 and moderate stretch factor
• Emanation graph: a plane geometric spanner with Steiner points
• Towards plane spanners of degree 3
• Degree four plane spanners: simpler and better
• Degree four plane spanners: simpler and better
• Plane Spanners of Maximum Degree Six
• Towards plane spanners of degree 3
• Diamond Triangulations Contain Spanners of Bounded Degree

This page was built for publication: There are Plane Spanners of Maximum Degree 4

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