TY - GEN
T1 - On the edge crossing properties of Euclidean minimum weight Laman graphs
AU - Bereg, Sergey
AU - Hong, Seok Hee
AU - Katoh, Naoki
AU - Poon, Sheung Hung
AU - Tanigawa, Shin Ichi
N1 - Funding Information:
This research was partially supported by the University of Sydney through a grant from the International Program Development Fund.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84893412261&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-45030-3_4
DO - 10.1007/978-3-642-45030-3_4
M3 - Conference contribution
AN - SCOPUS:84893412261
SN - 9783642450297
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 33
EP - 43
BT - Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
T2 - 24th International Symposium on Algorithms and Computation, ISAAC 2013
Y2 - 16 December 2013 through 18 December 2013
ER -