The number of disk graphs

DOI10.1016/J.EJC.2013.06.037MaRDI QIDQ2509768zbMATH OpenOpenAlexFDO

Authors Tobias Müller, Colin McDiarmid

Publication date 29 July 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2013.06.037

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Recommendations

• Counting disk graphs
• Integer realizations of disk and segment graphs
• Unit disk graphs
• Simple heuristics for unit disk graphs
• The number of bits needed to represent a unit disk graph

Cites work

• A Course in Enumeration
• A parallel algorithmic version of the local lemma
• Approximation and Online Algorithms
• Degrees of freedom versus dimension for containment orders
• Efficient graph representations
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1150554 (Why is no real title available?)
• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3223507 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3053541 (Why is no real title available?)
• Lower Bounds for Approximation by Nonlinear Manifolds
• On coloring unit disk graphs
• On the Betti Numbers of Real Varieties
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Robust algorithms for restricted domains
• Simple heuristics for unit disk graphs
• The number of polytopes, configurations and real matroids
• Unit disk graph recognition is NP-hard
• Unit disk graphs
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)

Cited in

(17)

• Integer realizations of disk and segment graphs
• Arrangements of orthogonal circles with many intersections
• On the speed of algebraically defined graph classes
• On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon
• A new characterization of disk graphs and its application.
• Counting disk graphs
• The number of bits needed to represent a unit disk graph
• Side disks of a spherical great polygon
• Arrangements of orthogonal circles with many intersections
• Refining the hierarchies of classes of geometric intersection graphs
• Approximation and Online Algorithms
• scientific article; zbMATH DE number 7765415 (Why is no real title available?)
• Moduli spaces of geometric graphs
• Enumeration of intersection graphs of x-monotone curves
• Local certification of geometric graph classes
• On forbidden induced subgraphs for unit disk graphs
• Sparse hop spanners for unit disk graphs

This page was built for publication: The number of disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509768)