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.1007/978-3-642-45030-3_4

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: Chapter in Book/Conference proceeding › Conference contribution › peer-review

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
Title of host publication	Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
Pages	33-43
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-45030-3_4
Publication status	Published - 2013
Externally published	Yes
Event	24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China Duration: 16 Dec 2013 → 18 Dec 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8283 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Symposium on Algorithms and Computation, ISAAC 2013
Country/Territory	China
City	Hong Kong
Period	16/12/13 → 18/12/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-45030-3_4

Cite this

Bereg, S., Hong, S. H., Katoh, N., Poon, S. H., & Tanigawa, S. I. (2013). On the edge crossing properties of Euclidean minimum weight Laman graphs. In Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings (pp. 33-43). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8283 LNCS). https://doi.org/10.1007/978-3-642-45030-3_4

@inproceedings{1f754fd964b4456abcb5754bf75e9c2f,

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.",

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

note = "Funding Information: This research was partially supported by the University of Sydney through a grant from the International Program Development Fund.; 24th International Symposium on Algorithms and Computation, ISAAC 2013 ; Conference date: 16-12-2013 Through 18-12-2013",

year = "2013",

doi = "10.1007/978-3-642-45030-3_4",

language = "English",

isbn = "9783642450297",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "33--43",

booktitle = "Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings",

}

Bereg, S, Hong, SH, Katoh, N, Poon, SH & Tanigawa, SI 2013, On the edge crossing properties of Euclidean minimum weight Laman graphs. in Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8283 LNCS, pp. 33-43, 24th International Symposium on Algorithms and Computation, ISAAC 2013, Hong Kong, China, 16/12/13. https://doi.org/10.1007/978-3-642-45030-3_4

On the edge crossing properties of Euclidean minimum weight Laman graphs. / Bereg, Sergey; Hong, Seok Hee; Katoh, Naoki et al.
Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. 2013. p. 33-43 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8283 LNCS).

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

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 -

Bereg S, Hong SH, Katoh N, Poon SH, Tanigawa SI. On the edge crossing properties of Euclidean minimum weight Laman graphs. In Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. 2013. p. 33-43. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-45030-3_4

On the edge crossing properties of Euclidean minimum weight Laman graphs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this