Proximity graphs: E, δ, Δ, χ and ω

Prosenjit Bose; Vida Dujmović; Ferran Hurtado; John Iacono; Stefan Langerman; Henk Meijer; Vera Sacristán; Maria Saumell; David R. Wood

doi:10.1142/S0218195912500112

Proximity graphs: E, δ, Δ, χ and ω

Prosenjit Bose, Vida Dujmović, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Vera Sacristán, Maria Saumell, David R. Wood

Research output: Contribution to journal › Article › peer-review

Abstract

Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. In the second part of the paper we focus on the higher order versions of some of these graphs and give bounds on the same parameters.

Original language	English (US)
Pages (from-to)	439-469
Number of pages	31
Journal	International Journal of Computational Geometry and Applications
Volume	22
Issue number	5
DOIs	https://doi.org/10.1142/S0218195912500112
State	Published - Oct 2012

Keywords

Geometric graphs
graph-theoretic properties
proximity graphs

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Theory and Mathematics
Computational Mathematics
Applied Mathematics

Access to Document

10.1142/S0218195912500112

Cite this

@article{74184c88b8a94ae582b8a50cdf2c0e14,

title = "Proximity graphs: E, δ, Δ, χ and ω",

abstract = "Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. In the second part of the paper we focus on the higher order versions of some of these graphs and give bounds on the same parameters.",

keywords = "Geometric graphs, graph-theoretic properties, proximity graphs",

author = "Prosenjit Bose and Vida Dujmovi{\'c} and Ferran Hurtado and John Iacono and Stefan Langerman and Henk Meijer and Vera Sacrist{\'a}n and Maria Saumell and Wood, {David R.}",

note = "Funding Information: for Spain. M. S. is supported by GraDR EUROGIGA project No. GIG/11/E023, and in part by projects MTM2009-07242 and Gen. Cat. DGR 2009SGR1040. D. W. is supported by the Australian Research Council.",

year = "2012",

month = oct,

doi = "10.1142/S0218195912500112",

language = "English (US)",

volume = "22",

pages = "439--469",

journal = "International Journal of Computational Geometry and Applications",

issn = "0218-1959",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "5",

}

TY - JOUR

T1 - Proximity graphs

T2 - E, δ, Δ, χ and ω

AU - Bose, Prosenjit

AU - Dujmović, Vida

AU - Hurtado, Ferran

AU - Iacono, John

AU - Langerman, Stefan

AU - Meijer, Henk

AU - Sacristán, Vera

AU - Saumell, Maria

AU - Wood, David R.

N1 - Funding Information: for Spain. M. S. is supported by GraDR EUROGIGA project No. GIG/11/E023, and in part by projects MTM2009-07242 and Gen. Cat. DGR 2009SGR1040. D. W. is supported by the Australian Research Council.

PY - 2012/10

Y1 - 2012/10

N2 - Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. In the second part of the paper we focus on the higher order versions of some of these graphs and give bounds on the same parameters.

AB - Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. In the second part of the paper we focus on the higher order versions of some of these graphs and give bounds on the same parameters.

KW - Geometric graphs

KW - graph-theoretic properties

KW - proximity graphs

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

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

U2 - 10.1142/S0218195912500112

DO - 10.1142/S0218195912500112

M3 - Article

AN - SCOPUS:84874035162

SN - 0218-1959

VL - 22

SP - 439

EP - 469

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 5

ER -

Proximity graphs: E, δ, Δ, χ and ω

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this