Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414613 | Computational Geometry | 2016 | 10 Pages |
Abstract
This paper is concerned with the crossing number of Euclidean minimum-weight Laman graphs in the plane. We first investigate the relation between the Euclidean minimum-weight Laman graph and proximity graphs, and then we show that the Euclidean minimum-weight Laman graph is quasi-planar and 6-planar. Thus the crossing number of the Euclidean minimum-weight Laman graph is linear in the number of points.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sergey Bereg, Seok-Hee Hong, Naoki Katoh, Sheung-Hung Poon, Shin-ichi Tanigawa,