Sphere and dot product representations of graphs

DOI10.1007/s00454-012-9394-8zbMath1238.05180OpenAlexW2115124828MaRDI QIDQ411410

Ross J. Kang, Tobias Müller

Publication date: 4 April 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-012-9394-8

zbMATH Keywords

sphericitydot product dimensiongeometric representations of graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (26)

On Embeddability of Unit Disk Graphs onto Straight Lines ⋮ Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs ⋮ The Complexity of Drawing a Graph in a Polygonal Region ⋮ What graphs are 2-dot product graphs? ⋮ Conflict-Free Coloring of Intersection Graphs ⋮ On embeddability of unit disk graphs onto straight lines ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ On complexity of multidistance graph recognition in \(\mathbb{R}^1\) ⋮ Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality ⋮ Logical labeling schemes ⋮ On arrangements of orthogonal circles ⋮ Unnamed Item ⋮ Random geometric complexes and graphs on Riemannian manifolds in the thermodynamic limit ⋮ Implicit representation conjecture for semi-algebraic graphs ⋮ Fixed points, Nash equilibria, and the existential theory of the reals ⋮ Intersection graphs of non-crossing paths ⋮ Computing a maximum clique in geometric superclasses of disk graphs ⋮ Global Rigidity of Unit Ball Graphs ⋮ Balanced line separators of unit disk graphs ⋮ Unnamed Item ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ \( L ( 2 , 1 )\)-labeling of disk intersection graphs ⋮ Unnamed Item ⋮ On the Complexity of Some Geometric Problems With Fixed Parameters ⋮ What Graphs are 2-Dot Product Graphs?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space graphs and sphericity
• Realizability of combinatorial types of convex polyhedra over fields
• On embedding of graphs into Euclidean spaces of small dimension
• Dot product representations of graphs
• Unit disk graph recognition is NP-hard
• Efficient graph representations
• Embeddings of graphs in Euclidean spaces
• Geometrical embeddings of graphs
• Threshold graphs and related topics
• Integer realizations of disk and segment graphs
• Optimal greedy algorithms for indifference graphs
• The Number of Bits Needed to Represent a Unit Disk Graph
• Implicat Representation of Graphs
• On the combinatorial and algebraic complexity of quantifier elimination
• Oriented Matroids
• Algorithms in real algebraic geometry

This page was built for publication: Sphere and dot product representations of graphs