Representing graphs by disks and balls (a survey of recognition-complexity results)
From MaRDI portal
Publication:5931448
DOI10.1016/S0012-365X(00)00204-1zbMath0969.68118MaRDI QIDQ5931448
Publication date: 7 October 2001
Published in: Discrete Mathematics (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (28)
Contact Representations of Graphs in 3D ⋮ Intersection graphs of homothetic polygons ⋮ A tight bound for online colouring of disk graphs ⋮ Unit disk representations of embedded trees, outerplanar and multi-legged graphs ⋮ Arrangements of orthogonal circles with many intersections ⋮ Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Intersection graphs of maximal sub-polygons of \(k\)-lizards ⋮ On contact numbers of totally separable unit sphere packings ⋮ Harmonic functions of polynomial growth on infinite penny graphs ⋮ Approximation Algorithms for Geometric Intersection Graphs ⋮ Optimal polygonal representation of planar graphs ⋮ Contact graphs of ball packings ⋮ Representing graphs and hypergraphs by touching polygons in 3D ⋮ On arrangements of orthogonal circles ⋮ Contact graphs of unit sphere packings revisited ⋮ Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count ⋮ On distance constrained labeling of disk graphs ⋮ Arrangements of orthogonal circles with many intersections ⋮ Sphericity, cubicity, and edge clique covers of graphs ⋮ The number of disk graphs ⋮ Analogs of Steiner's porism and Soddy's hexlet in higher dimensions via spherical codes ⋮ Discrete harmonic functions on infinite penny graphs ⋮ Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs ⋮ \( L ( 2 , 1 )\)-labeling of disk intersection graphs ⋮ Weak Unit Disk and Interval Representation of Graphs ⋮ On the Complexity of Some Geometric Problems With Fixed Parameters ⋮ On-line coloring of geometric intersection graphs
This page was built for publication: Representing graphs by disks and balls (a survey of recognition-complexity results)
