On the edge crossing properties of Euclidean minimum weight Laman graphs

Sergey Bereg, Seok Hee Hong, Naoki Katoh, Sheung Hung Poon, Shin Ichi Tanigawa

Research output: Journal PublicationArticlepeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Pages (from-to)15-24
Number of pages10
JournalComputational Geometry: Theory and Applications
Volume51
DOIs
Publication statusPublished - Jan 2016
Externally publishedYes

Keywords

  • (k,l)-Sparse graphs
  • Laman graphs
  • Plane graphs
  • Quasi-planarity
  • k-Planarity

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'On the edge crossing properties of Euclidean minimum weight Laman graphs'. Together they form a unique fingerprint.

Cite this