Premium
Proximity graphs inside large weighted graphs
Author(s) -
Ábrego Bernardo M.,
FabilaMonroy Ruy,
FernándezMerchant Silvia,
FloresPeñaloza David,
Hurtado Ferran,
Meijer Henk,
Sacristán Vera,
Saumell Maria
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21464
Subject(s) - combinatorics , vertex (graph theory) , mathematics , euclidean geometry , shortest path problem , indifference graph , discrete mathematics , graph , computer science , geometry
Given a weighted graph G = ( V , E ) and a subset U of V , we define several graphs with vertex set U in which two vertices are adjacent if they satisfy a specific proximity rule. These rules use the shortest path distance in G and generalize the proximity rules that generate some of the most common proximity graphs in Euclidean spaces. We prove basic properties of the defined graphs and provide algorithms for their computation. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013