On the edge crossing properties of Euclidean minimum weight Laman graphs

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

doi:10.1016/j.comgeo.2015.10.002

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 Publication › Article › peer-review

3 Citations (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 language	English
Pages (from-to)	15-24
Number of pages	10
Journal	Computational Geometry: Theory and Applications
Volume	51
DOIs	https://doi.org/10.1016/j.comgeo.2015.10.002
Publication status	Published - Jan 2016
Externally published	Yes

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

Access to Document

10.1016/j.comgeo.2015.10.002

Cite this

@article{79899e5d1ff241b4b075bcd2d2006184,

title = "On the edge crossing properties of Euclidean minimum weight Laman graphs",

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 = "(k,l)-Sparse graphs, Laman graphs, Plane graphs, Quasi-planarity, k-Planarity",

author = "Sergey Bereg and Hong, {Seok Hee} and Naoki Katoh and Poon, {Sheung Hung} and Tanigawa, {Shin Ichi}",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2016",

month = jan,

doi = "10.1016/j.comgeo.2015.10.002",

language = "English",

volume = "51",

pages = "15--24",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

}

TY - JOUR

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

PY - 2016/1

Y1 - 2016/1

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.

KW - (k,l)-Sparse graphs

KW - Laman graphs

KW - Plane graphs

KW - Quasi-planarity

KW - k-Planarity

UR - http://www.scopus.com/inward/record.url?scp=84945208178&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2015.10.002

DO - 10.1016/j.comgeo.2015.10.002

M3 - Article

AN - SCOPUS:84945208178

SN - 0925-7721

VL - 51

SP - 15

EP - 24

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

ER -

On the edge crossing properties of Euclidean minimum weight Laman graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this