Generalized Disk Graphs

Ívar Marrow Arnþórsson; Steven Chaplick; Jökull Snær Gylfason; Magnús M. Halldórsson; Jökull Máni Reynisson; Tigran Tonoyan

doi:10.1007/978-3-030-83508-8_9

Generalized Disk Graphs

Ívar Marrow Arnþórsson, Steven Chaplick, Jökull Snær Gylfason, Magnús M. Halldórsson, Jökull Máni Reynisson, Tigran Tonoyan^*

^*Corresponding author for this work

Department of Computer Science

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

Abstract

A graph G is a Generalized Disk Graph if for some dimension η≥ 1, a non-decreasing sub-linear function f and natural number t, each vertex v_i can be assigned a length l_i and set P_i⊆ R^η of t points such that v_iv_j is an edge of G if and only if l_i≤ l_j and d(Pi,Pj)≤lif(lj/li)+lif(1), where d(·, · ) is the least distance between points in either set. Generalized disk graphs were introduced as a model of wireless network interference and have been shown to be dramatically more accurate than disk graphs or other previously known graph classes. However, their properties have not been studied extensively before. We give a geometric representation of these graphs as intersection graphs of convex shapes, relate them to other geometric intersection graph classes, and solve several important optimization problems on these graphs using the geometric representation; either exactly (in two-dimensions) or approximately (in higher dimensions).

Original language	English
Title of host publication	Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings
Editors	Anna Lubiw, Mohammad Salavatipour
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	115-128
Number of pages	14
ISBN (Print)	9783030835071
DOIs	https://doi.org/10.1007/978-3-030-83508-8_9
Publication status	Published - 2021
Event	17th International Symposium on Algorithms and Data Structures, WADS 2021 - Virtual, Online Duration: 9 Aug 2021 → 11 Aug 2021

Publication series

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

Conference

Conference	17th International Symposium on Algorithms and Data Structures, WADS 2021
City	Virtual, Online
Period	9/08/21 → 11/08/21

Bibliographical note

Funding Information:
Work supported by grant 174484-051 from Icelandic Research Fund and grant 208348-0091 from Icelandic Student Innovation Fund.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Other keywords

Conflict graph
Intersection graph
SINR model

Access to Document

10.1007/978-3-030-83508-8_9

Cite this

Arnþórsson, Í. M., Chaplick, S., Gylfason, J. S., Halldórsson, M. M., Reynisson, J. M., & Tonoyan, T. (2021). Generalized Disk Graphs. In A. Lubiw, & M. Salavatipour (Eds.), Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings (pp. 115-128). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12808 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-83508-8_9

Arnþórsson, Ívar Marrow ; Chaplick, Steven ; Gylfason, Jökull Snær et al. / Generalized Disk Graphs. Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings. editor / Anna Lubiw ; Mohammad Salavatipour. Springer Science and Business Media Deutschland GmbH, 2021. pp. 115-128 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9d1490bb3efe4dcd852ef202dc6e2d3a,

title = "Generalized Disk Graphs",

abstract = "A graph G is a Generalized Disk Graph if for some dimension η≥ 1, a non-decreasing sub-linear function f and natural number t, each vertex vi can be assigned a length li and set Pi⊆ Rη of t points such that vivj is an edge of G if and only if li≤ lj and d(Pi,Pj)≤lif(lj/li)+lif(1), where d(·, · ) is the least distance between points in either set. Generalized disk graphs were introduced as a model of wireless network interference and have been shown to be dramatically more accurate than disk graphs or other previously known graph classes. However, their properties have not been studied extensively before. We give a geometric representation of these graphs as intersection graphs of convex shapes, relate them to other geometric intersection graph classes, and solve several important optimization problems on these graphs using the geometric representation; either exactly (in two-dimensions) or approximately (in higher dimensions).",

keywords = "Conflict graph, Intersection graph, SINR model",

author = "Arn{\th}{\'o}rsson, {{\'I}var Marrow} and Steven Chaplick and Gylfason, {J{\"o}kull Sn{\ae}r} and Halld{\'o}rsson, {Magn{\'u}s M.} and Reynisson, {J{\"o}kull M{\'a}ni} and Tigran Tonoyan",

note = "Funding Information: Work supported by grant 174484-051 from Icelandic Research Fund and grant 208348-0091 from Icelandic Student Innovation Fund. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 17th International Symposium on Algorithms and Data Structures, WADS 2021 ; Conference date: 09-08-2021 Through 11-08-2021",

year = "2021",

doi = "10.1007/978-3-030-83508-8_9",

language = "English",

isbn = "9783030835071",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "115--128",

editor = "Anna Lubiw and Mohammad Salavatipour",

booktitle = "Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings",

address = "Germany",

}

Arnþórsson, ÍM, Chaplick, S, Gylfason, JS, Halldórsson, MM, Reynisson, JM & Tonoyan, T 2021, Generalized Disk Graphs. in A Lubiw & M Salavatipour (eds), Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12808 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 115-128, 17th International Symposium on Algorithms and Data Structures, WADS 2021, Virtual, Online, 9/08/21. https://doi.org/10.1007/978-3-030-83508-8_9

Generalized Disk Graphs. / Arnþórsson, Ívar Marrow; Chaplick, Steven; Gylfason, Jökull Snær et al.
Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings. ed. / Anna Lubiw; Mohammad Salavatipour. Springer Science and Business Media Deutschland GmbH, 2021. p. 115-128 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12808 LNCS).

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

TY - GEN

T1 - Generalized Disk Graphs

AU - Arnþórsson, Ívar Marrow

AU - Chaplick, Steven

AU - Gylfason, Jökull Snær

AU - Halldórsson, Magnús M.

AU - Reynisson, Jökull Máni

AU - Tonoyan, Tigran

N1 - Funding Information: Work supported by grant 174484-051 from Icelandic Research Fund and grant 208348-0091 from Icelandic Student Innovation Fund. Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - A graph G is a Generalized Disk Graph if for some dimension η≥ 1, a non-decreasing sub-linear function f and natural number t, each vertex vi can be assigned a length li and set Pi⊆ Rη of t points such that vivj is an edge of G if and only if li≤ lj and d(Pi,Pj)≤lif(lj/li)+lif(1), where d(·, · ) is the least distance between points in either set. Generalized disk graphs were introduced as a model of wireless network interference and have been shown to be dramatically more accurate than disk graphs or other previously known graph classes. However, their properties have not been studied extensively before. We give a geometric representation of these graphs as intersection graphs of convex shapes, relate them to other geometric intersection graph classes, and solve several important optimization problems on these graphs using the geometric representation; either exactly (in two-dimensions) or approximately (in higher dimensions).

AB - A graph G is a Generalized Disk Graph if for some dimension η≥ 1, a non-decreasing sub-linear function f and natural number t, each vertex vi can be assigned a length li and set Pi⊆ Rη of t points such that vivj is an edge of G if and only if li≤ lj and d(Pi,Pj)≤lif(lj/li)+lif(1), where d(·, · ) is the least distance between points in either set. Generalized disk graphs were introduced as a model of wireless network interference and have been shown to be dramatically more accurate than disk graphs or other previously known graph classes. However, their properties have not been studied extensively before. We give a geometric representation of these graphs as intersection graphs of convex shapes, relate them to other geometric intersection graph classes, and solve several important optimization problems on these graphs using the geometric representation; either exactly (in two-dimensions) or approximately (in higher dimensions).

KW - Conflict graph

KW - Intersection graph

KW - SINR model

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

U2 - 10.1007/978-3-030-83508-8_9

DO - 10.1007/978-3-030-83508-8_9

M3 - Conference contribution

AN - SCOPUS:85113564711

SN - 9783030835071

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 115

EP - 128

BT - Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings

A2 - Lubiw, Anna

A2 - Salavatipour, Mohammad

PB - Springer Science and Business Media Deutschland GmbH

T2 - 17th International Symposium on Algorithms and Data Structures, WADS 2021

Y2 - 9 August 2021 through 11 August 2021

ER -

Arnþórsson ÍM, Chaplick S, Gylfason JS, Halldórsson MM, Reynisson JM, Tonoyan T. Generalized Disk Graphs. In Lubiw A, Salavatipour M, editors, Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 115-128. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-83508-8_9

Generalized Disk Graphs

Abstract

Publication series

Conference

Bibliographical note

Other keywords

Access to Document

Fingerprint

Cite this